oj.uz

Submission #502283

# Submission time Handle Problem Language Result Execution time Memory
502283 2022-01-05T17:22:00 Z benedict0724 None (JOI16_ho_t3) C++17
0 / 100
 80 ms 12828 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e8;

int u[200002], v[200002], ans[200002], dist[100002], R[200002], nes[200002], path[100002], siz[200002];
vector<int> adj[100002];

int f(int x)
{
    if(x == path[x]) return x;
    return path[x] = f(path[x]);
}

void uni(int x, int y)
{
    x = f(x); y = f(y);
    if(x == y) return;
    path[x] = y;
    siz[y] += siz[x];
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int N, M, Q; cin >> N >> M >> Q;
    for(int i=1;i<=M;i++)
    {
        cin >> u[i] >> v[i];
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }

    for(int i=1;i<=Q;i++) cin >> R[i];

    for(int i=2;i<=N;i++) dist[i] = INF;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        for(int i : adj[now])
        {
            if(dist[i] > dist[now] + 1)
            {
                dist[i] = dist[now] + 1;
                q.push(i);
            }
        }
    }

    for(int i=1;i<=M;i++)
    {
        if(dist[u[i]] != dist[v[i]]) nes[i] = 1;
    }

    for(int i=1;i<=Q;i++) nes[R[i]] = 0;
    for(int i=1;i<=N;i++)
    {
        path[i] = i;
        siz[i] = 1;
    }

    for(int i=1;i<=M;i++)
    {
        if(nes[i])
        {
            uni(u[i], v[i]);
        }
    }
    for(int i=Q;i>=1;i--)
    {
        ans[i] = N - siz[f(1)];
        if(dist[u[R[i]]] != dist[v[R[i]]]) uni(u[R[i]], v[R[i]]);
    }

    for(int i=1;i<=Q;i++) cout << ans[i] << "\n";
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2664 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2664 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 12828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2664 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -