oj.uz

Submission #545440

# Submission time Handle Problem Language Result Execution time Memory
545440 2022-04-04T14:12:37 Z pokmui9909 None (JOI16_ho_t3) C++17
12 / 100
 145 ms 21600 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
ll N, M, K;
pair<ll, ll> E[200005];
vector<pair<ll, ll>> G[100005];
ll dist[100005];
const ll INF = 1e18;
ll deg[100005];
ll chk[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N >> M >> K;
    for(int i = 1; i <= M; i++){
        cin >> E[i].x >> E[i].y;
        G[E[i].x].push_back({E[i].y, i});
        G[E[i].y].push_back({E[i].x, i});
    }
    queue<ll> Q;
    fill(dist, dist + N + 1, INF);
    Q.push(1); dist[1] = 0;
    while(!Q.empty()){
        ll u = Q.front(); Q.pop();
        for(auto i : G[u]){
            if(dist[i.x] <= dist[u] + 1) continue;
            dist[i.x] = dist[u] + 1;
            Q.push(i.x);
        }
    }
    for(int i = 1; i <= M; i++){
        if(dist[E[i].x] == dist[E[i].y]) continue;
        if(dist[E[i].x] > dist[E[i].y]) swap(E[i].x, E[i].y);
        deg[E[i].y]++;
    }
    ll r = 0;
    while(K--){
        ll t; cin >> t;
        if(!chk[t] && dist[E[t].x] != dist[E[t].y]){
            Q.push(t); chk[t] = 1, deg[E[t].y]--;
            while(!Q.empty()){
                ll u = Q.front(); Q.pop();
                if(deg[E[u].y] == 0){
                    r++;
                    for(auto i : G[E[u].y]){
                        if(chk[i.y] || dist[E[i.y].x] == dist[E[i.y].y]) continue;
                        chk[i.y] = 1, deg[E[i.y].y]--;
                        Q.push(i.y);
                    }
                }
            }
        }
        cout << r << '\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2956 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2700 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2956 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2700 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 118 ms 20388 KB Output is correct
10 Correct 145 ms 20524 KB Output is correct
11 Correct 95 ms 19600 KB Output is correct
12 Correct 103 ms 19832 KB Output is correct
13 Correct 103 ms 19936 KB Output is correct
14 Correct 98 ms 19856 KB Output is correct
15 Incorrect 73 ms 14412 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 21600 KB Output is correct
2 Correct 124 ms 21440 KB Output is correct
3 Correct 96 ms 16184 KB Output is correct
4 Correct 112 ms 20280 KB Output is correct
5 Correct 106 ms 20016 KB Output is correct
6 Correct 116 ms 20044 KB Output is correct
7 Correct 62 ms 12568 KB Output is correct
8 Correct 52 ms 12448 KB Output is correct
9 Correct 30 ms 10752 KB Output is correct
10 Correct 30 ms 10872 KB Output is correct
11 Correct 124 ms 20912 KB Output is correct
12 Correct 111 ms 20264 KB Output is correct
13 Correct 123 ms 19916 KB Output is correct
14 Correct 123 ms 21580 KB Output is correct
15 Incorrect 123 ms 20128 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2956 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2700 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 118 ms 20388 KB Output is correct
10 Correct 145 ms 20524 KB Output is correct
11 Correct 95 ms 19600 KB Output is correct
12 Correct 103 ms 19832 KB Output is correct
13 Correct 103 ms 19936 KB Output is correct
14 Correct 98 ms 19856 KB Output is correct
15 Incorrect 73 ms 14412 KB Output isn't correct
16 Halted 0 ms 0 KB -