oj.uz

Submission #502293

# Submission time Handle Problem Language Result Execution time Memory
502293 2022-01-05T17:45:56 Z benedict0724 None (JOI16_ho_t3) C++17
0 / 100
 99 ms 12348 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], use[100002];
vector<pair<int, int>> adj[100002];

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], i});
        adj[v[i]].push_back({u[i], 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(auto uv : adj[now])
        {
            int i = uv.first;
            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;

    q.push(1);
    int tmp = 0;
    while(!q.empty())
    {
        int now = q.front(); q.pop();
        use[now] = 1;
        tmp++;
        for(auto uv : adj[now])
        {
            if(!nes[uv.second]) continue;
            int i = uv.first;
            if(dist[i] == dist[now] + 1) q.push(i);
        }
    }

    for(int i=Q;i>=1;i--)
    {
        ans[i] = N - tmp;
        if(dist[u[R[i]]] == dist[v[R[i]]]) continue;
        nes[R[i]] = 1;
        int A, B;
        if(dist[u[R[i]]] > dist[v[R[i]]])
        {
            A = v[R[i]];
            B = u[R[i]];
        }
        else
        {
            A = u[R[i]];
            B = v[R[i]];
        }

        if(use[A] && !use[B])
        {
            q.push(B);
            while(!q.empty())
            {
                int now = q.front(); q.pop();
                tmp++;
                use[now] = 1;
                for(auto uv: adj[now])
                {
                    if(!nes[uv.second]) continue;
                    int j = uv.first;
                    if(dist[j] == dist[now] + 1 && !use[j]) q.push(j);
                }
            }
        }
    }

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

Subtask #1
0 / 12.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 39.0

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