Submission #1126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126		tncks0121	Synchronization (JOI13_synchronization)	C++98	30 / 100	100 ms	17708 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40