oj.uz

Submission #51179

# Submission time Handle Problem Language Result Execution time Memory
51179 2018-06-17T05:20:28 Z 노영훈(#1283, Diuven) None (JOI16_ho_t3) C++11
26 / 100
 160 ms 10492 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MX=100010, inf=2e9;

struct edge {
    int u, v;
} E[2*MX];
vector<int> G[MX];

int n, m, q;
int up_deg[MX];
int dep[MX];
int ans;
bool done[MX];

void init(){
    queue<int> Q;
    fill(dep, dep+n+1, -1);
    dep[1]=0; Q.push(1);
    while(!Q.empty()){
        int v=Q.front(); Q.pop();
        for(int x:G[v]){
            if(dep[x]==dep[v]+1) up_deg[x]++;
            if(dep[x]<0){
                dep[x]=dep[v]+1; up_deg[x]++;
                Q.push(x);
            }
        }
    }
}

void down(int v){
    //cout<<"OUT: "<<v<<'\n';
    ans++;
    done[v]=true;
    for(int x:G[v]){
        if(dep[x]<=dep[v] || done[x]) continue;
        up_deg[x]--;
        if(up_deg[x]==0) down(x);
    }
}

void upt(int r){
    int a=E[r].u, b=E[r].v;
    if(dep[a]==dep[b]) return;
    if(dep[a]>dep[b]) swap(a,b);
    if(done[a]) return;
    // a is upper
    up_deg[b]--;
    if(up_deg[b]==0){
        down(b);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1, u, v; i<=m; i++){
        cin>>u>>v;
        E[i]={u,v};
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init();
    for(int i=1, r; i<=q; i++){
        cin>>r;
        upt(r);
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2992 KB Output is correct
4 Correct 5 ms 2992 KB Output is correct
5 Correct 5 ms 2992 KB Output is correct
6 Correct 4 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 4 ms 2992 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2992 KB Output is correct
4 Correct 5 ms 2992 KB Output is correct
5 Correct 5 ms 2992 KB Output is correct
6 Correct 4 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 4 ms 2992 KB Output is correct
9 Correct 160 ms 9740 KB Output is correct
10 Correct 141 ms 9740 KB Output is correct
11 Correct 132 ms 9740 KB Output is correct
12 Correct 110 ms 9740 KB Output is correct
13 Correct 122 ms 9740 KB Output is correct
14 Correct 114 ms 9740 KB Output is correct
15 Correct 96 ms 10492 KB Output is correct
16 Correct 59 ms 10492 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 5 ms 2992 KB Output is correct
4 Correct 5 ms 2992 KB Output is correct
5 Correct 5 ms 2992 KB Output is correct
6 Correct 4 ms 2992 KB Output is correct
7 Correct 5 ms 2992 KB Output is correct
8 Correct 4 ms 2992 KB Output is correct
9 Correct 160 ms 9740 KB Output is correct
10 Correct 141 ms 9740 KB Output is correct
11 Correct 132 ms 9740 KB Output is correct
12 Correct 110 ms 9740 KB Output is correct
13 Correct 122 ms 9740 KB Output is correct
14 Correct 114 ms 9740 KB Output is correct
15 Correct 96 ms 10492 KB Output is correct
16 Correct 59 ms 10492 KB Output is correct
17 Incorrect 120 ms 10492 KB Output isn't correct
18 Halted 0 ms 0 KB -