CSP-S 2022 星战（神题）

Skyzhou666 · 2022-11-16 13:32:32 · 题解

考场先开T3，敲了两个小时模拟还写挂了，只有30pts

回来一看，这个赋随机权值是真的离谱

#include <iostream>
#include <vector>
#include <time.h>
#define MAXN 500001
using namespace std;

int n, m, q, in[MAXN], out[MAXN], w[MAXN];

int main()
{
    cin >> n >> m;
    srand((unsigned)time(NULL));
    int check = 0, now = 0;
    for(int x = 1; x <= n; x++) w[x] = rand() % 114514, check += w[x];
    for(int x = 1; x <= m; x++)
    {
        int u, v;
        cin >> u >> v;
        out[v] += w[u];
        in[v] += w[u];
        now += w[u];
    }
    cin >> q;
    while(q--)
    {
        int t, u, v;
        cin >> t;
        //cout << "NO" << endl; fuck ccf
        if(t == 1)
        {
            cin >> u >> v;
            in[v] -= w[u];
            now -= w[u];
        }
        else if(t == 2)
        {
            cin >> u;
            now -= in[u];
            in[u] = 0;
        }
        else if(t == 3)
        {
            cin >> u >> v;
            in[v] += w[u];
            now += w[u];
        }
        else if(t == 4)
        {
            cin >> u;
            now += out[u] - in[u];
            in[u] = out[u];
        }
        if(now == check) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

最后请CCF不要用脚造数据让全输出NO的都拿了45pts！！！

唉找到了考场的垃圾代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define MAXN 1000001
using namespace std;

struct Edge
{
    int u, v;
};

vector <int> g[MAXN], fg[MAXN];
bool vis[MAXN], ish[MAXN];
int n, m, out[MAXN], in[MAXN], hucnt, suocnt;

void delEdge(int u, int v)
{
    for(vector<int>::iterator i = g[u].begin(); i != g[u].end(); i++)
    {
        if(*i == v)
        {
            //cout << "DEL" << v << endl;
            g[u].erase(i);
            if(out[u] == 2) suocnt++;
            else if(out[u] == 1) suocnt--;
            out[u]--;
            break;
        }
    }
}

void dfs(int u)
{
    if(ish[u]) return;
    vis[u] = true;
    for(int x = 0; x < g[u].size(); x++)
    {
        int v = g[u][x];
        if(!vis[u])
        {
            dfs(v);
            if(ish[v]) hucnt++;
            ish[u] = ish[v];
        }
        else
        {
            if(!ish[u]) hucnt++;
            ish[u] = true;
        }
    }
}

void checkAns()
{
    memset(vis, 0, sizeof(vis));
    memset(ish, 0, sizeof(ish));
    hucnt = 0;
    for(int x = 1; x <= n; x++)
        if(!vis[x]) dfs(x);
    //cout << "SUO: ";
    //for(int x = 1; x <= n; x++) cout << out[x] << " ";
    //cout << endl;
    //cout << "CNT: " << hucnt << " " << suocnt << endl;
    if(hucnt == n && suocnt == n) cout << "YES" << endl;
    else cout << "NO" << endl;
}

bool find(int u, int v)
{
    bool re = false;
    for(int x = 0; x < g[u].size(); x++)
    {
        int vv = g[u][x];
        if(vv == v)
        {
            re = true;
            break;
        }
    }
}

int main()
{
    freopen("galaxy.in", "r", stdin);
    freopen("galaxy.out", "w", stdout);

    int q;
    cin >> n >> m;
    for(int x = 0; x < m; x++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        fg[v].push_back(u);
        if(out[u] == 0) suocnt++;
        else if(out[u] == 1) suocnt--;
        out[u]++;
    }
    //cout << "SUO: " << suocnt << endl;
    cin >> q;
    while(q--)
    {
        int t, u, v;
        cin >> t;
        if(t == 1)
        {
            cin >> u >> v;
            delEdge(u, v);
        }
        else if(t == 2)
        {
            cin >> u;
            for(int x = 0; x < fg[u].size(); x++)
            {
                int v = fg[u][x];
                delEdge(v, u);
            }
        }
        else if(t == 3)
        {
            cin >> u >> v;
            g[u].push_back(v);
            if(out[u] == 0) suocnt++;
            else if(out[u] == 1) suocnt--;
            out[u]++;
        }
        else if(t == 4)
        {
            cin >> u;
            for(int x = 0; x < fg[u].size(); x++)
            {
                int v = fg[u][x];
                if(find(v, u)) continue;
                g[v].push_back(u);
                if(out[v] == 0) suocnt++;
                else if(out[v] == 1) suocnt--;
                out[v]++;
            }
        }
        checkAns();
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}