oj.uz

Submission #1126

# Submission time Handle Problem Language Result Execution time Memory
1126 2013-06-26T07:43:56 Z tncks0121 Synchronization (JOI13_synchronization) C++
30 / 100
 100 ms 17708 KB 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
const int INF = 987654321; 
const ll LINF = 1e15;  

const int N_ = 200005;
const int M_ = 200005;
const int Q_ = N_;

int TIME, chk[N_];

int N, M, Q;
vector<int> Gph[N_];
int C[Q_], D[Q_], X[N_], Y[N_];

int parent[N_];
void DFS1 (int u) {
    int i;
    chk[u] = TIME;
    for(i = 0; i < Gph[u].size(); i++) {
        int v = Gph[u][i];
        if(chk[v] != TIME) {
            parent[v] = u;
            DFS1(v);
        }
    }
}

bool change[N_];

void DFS2 (int u) {
    chk[u] = TIME;
    for(int i = 0; i < Gph[u].size(); i++) {
        int v = Gph[u][i];
        if(chk[v] != TIME && change[v]) DFS2(v);
    }
}

int main() {
    int i, j, k;

	scanf("%d%d%d", &N, &M, &Q);
    for(i = 1; i < N; i++) {
        int u, v; scanf("%d%d", &u, &v);
        Gph[u].push_back(v);
        Gph[v].push_back(u);
        X[i] = u; Y[i] = v;
    }
    
    for(i = 1; i <= M; i++) scanf("%d", D+i);
    for(i = 1; i <= Q; i++) scanf("%d", C+i);
    
    if(Q == 1) {
        int r = C[1];
        ++TIME; DFS1(r);
        
        for(i = 1; i <= M; i++) {
            int &d = D[i];
            if(X[d] == parent[Y[d]]) d = Y[d];
            else d = X[d];
        }
        
        ++TIME;
        for(i = 1; i <= M; i++) change[D[i]] ^= true;
        DFS2(r);
        
        for(i = M; i > 0; i--) {
            int &d = D[i];
            change[d] ^= true;
            if(change[d] && chk[parent[d]] == TIME && chk[d] != TIME) DFS2(d);
        }
        
        int ret = 0;
        for(i = 1; i <= N; i++) {
            if(chk[i] == TIME) ++ret;
        }
        
        printf("%d\n", ret);
    }else {
        
    }
    
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10484 KB Output is correct
2 Correct 0 ms 10484 KB Output is correct
3 Correct 0 ms 10484 KB Output is correct
4 Correct 0 ms 10484 KB Output is correct
5 Correct 0 ms 10484 KB Output is correct
6 Correct 0 ms 10484 KB Output is correct
7 Correct 8 ms 10748 KB Output is correct
8 Correct 9 ms 10748 KB Output is correct
9 Correct 7 ms 10748 KB Output is correct
10 Correct 98 ms 13652 KB Output is correct
11 Correct 100 ms 13652 KB Output is correct
12 Correct 75 ms 16144 KB Output is correct
13 Correct 67 ms 14036 KB Output is correct
14 Correct 95 ms 13652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 16124 KB Output is correct
2 Correct 69 ms 15024 KB Output is correct
3 Correct 59 ms 17708 KB Output is correct
4 Correct 56 ms 17100 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 10480 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 13516 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 10480 KB Output isn't correct
2 Halted 0 ms 0 KB -
3 Halted 0 ms 0 KB -
4 Halted 0 ms 0 KB -
5 Halted 0 ms 0 KB -
6 Halted 0 ms 0 KB -
7 Halted 0 ms 0 KB -
8 Halted 0 ms 0 KB -
9 Halted 0 ms 0 KB -
10 Halted 0 ms 0 KB -
11 Halted 0 ms 0 KB -
12 Halted 0 ms 0 KB -
13 Halted 0 ms 0 KB -