啊,样例都过不了,为什么?!

P1197 [JSOI2008] 星球大战

卷王 @ 2023-01-21 10:50:54

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4000007;
struct node
{
    int nxt, to, from;
}e[maxn];
int n, m, k, x, y, tot, cnt = 0;
int h[maxn];
int a[maxn], f[maxn];
int ans[maxn];
bool vis[maxn];
inline int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
inline void add(int u, int v)
{
    e[++cnt].from = u;
    e[cnt].nxt = h[u];
    e[cnt].to = v;
    h[u] = cnt;
}
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        x = read(), y = read();
        add(x, y); add(y, x);
    }
    k = read();
    for(int i = 1; i <= k; i++)
    {
        a[i] = read();
        vis[a[i]] = 1;
    }
    tot = n - k;
    for(int i = 1; i <= m * 2; i++)
    {
        int u = e[i].from, v = e[i].to;
        if(vis[u] == 0 && vis[v] == 0 && f[find(u)] != f[find(v)])
        {
            tot--;
            f[find(u)] = f[find(v)];
        }
    }
    ans[k + 1] = tot;
    for(int i = k; i >= 1; i--)
    {
        int u = a[i]; vis[u] = 0;
        tot++;
        for(int j = h[u]; j; j = e[j].nxt)
        {
            int v = e[i].to;
            if(vis[v] == 0 && f[find(u)] != f[find(v)])
            {
                tot--;
                f[find(u)] = f[find(v)];
            }
        }
        ans[i] = tot;
    }
    for(int i = 1; i <= k + 1; i++)
        printf("%d\n", ans[i]);
    return 0;
}

by Algae_qwq @ 2023-01-21 11:20:07

头像好评


by Loser_Syx @ 2023-01-21 11:46:59

我记得lz之前的头像是kkk的


by W2011cx @ 2023-01-21 11:52:22

我甚至以为这是兔队的帖子


by Fragile_like_bomb @ 2023-01-21 12:05:39

mpft


|