oj.uz

Submission #25483

# Submission time Handle Problem Language Result Execution time Memory
25483 2017-06-22T11:31:22 Z kajebiii Synchronization (JOI13_synchronization) C++14
100 / 100
 5309 ms 23236 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e5 + 100;

int N, M, Q, Nr[MAX_N][2];
vector<pi> Ed[MAX_N];
int St[MAX_N], En[MAX_N], TN, Dep[MAX_N], P[MAX_N], Ix[MAX_N];
int Info[MAX_N], Up[MAX_N], TempUp[MAX_N], Memo[MAX_N];
bool State[MAX_N];
void dfs(int v, int p) {
	Dep[v] = Dep[p] + 1;
	St[v] = TN++; P[v] = p;
	Info[v] = 1; Up[v] = v;
	for(pi &e : Ed[v]) {
		int w, ix; tie(w, ix) = e;
		if(w != p) {
			Ix[w] = ix;
			dfs(w, v);
		}
	}
	En[v] = TN-1;
}
vector<int> Qs;
int getP(int v, int qi) {
	int p = Up[v];
	while(TempUp[p]) p = TempUp[p];
	for(int q=0; q<qi; q++) {
		int i = Qs[q];
		int a = Nr[i][0], b = Nr[i][1];
		if(State[Ix[b]] == false)
			if(St[b] <= St[v] && St[v] <= En[b])
				if(Dep[p] < Dep[b]) 
					p = b;
	}
	return p;
}
void cut(int qi) {
	int ix = Qs[qi];
	int a = Nr[ix][0], b = Nr[ix][1];
	int p = getP(a, qi);
	Memo[Ix[b]] = Info[b] = Info[p];
	TempUp[b] = p;
}
void link(int qi) {
	int ix = Qs[qi];
	int a = Nr[ix][0], b = Nr[ix][1];
	int p = getP(a, qi);
	Info[p] += Info[b] - Memo[Ix[b]];
	TempUp[b] = p;
}
void dfsUpdate(int v, int p, int r) {
	TempUp[v] = 0;
	Info[v] = Info[r];
	Up[v] = r;
	for(pi &e : Ed[v]) {
		int w, ix; tie(w, ix) = e;
		if(w != p) {
			if(State[Ix[w]]) dfsUpdate(w, v, r);
			else dfsUpdate(w, v, w);
		}
	}
}
void update() {
	for(int qi=0; qi<SZ(Qs); qi++) {
		int ix = Qs[qi];
		if(State[ix]) cut(qi);
		else link(qi);
		State[ix] = 1 - State[ix];
	}
	Qs.clear();
	dfsUpdate(1, 0, 1);
}
int main() {
	cin >> N >> M >> Q;
	REP(i, N-1) {
		int x, y; scanf("%d%d", &x, &y);
		Ed[x].push_back(pi(y, i)); Ed[y].push_back(pi(x, i));
		Nr[i][0] = x; Nr[i][1] = y;
	}
	dfs(1, 0);
	REP(i, N-1) if(Dep[Nr[i][0]] > Dep[Nr[i][1]]) swap(Nr[i][0], Nr[i][1]);

	int rM = 600; // 100000^0.5
	REP(i, M) {
		int ix; scanf("%d", &ix); ix--;
		Qs.push_back(ix);
		if(i+1 == M || SZ(Qs) == rM) update();
	}
	REP(i, Q) {
		int x; scanf("%d", &x);
		printf("%d\n", Info[x]);
	}
	return 0;
}

Compilation message

synchronization.cpp: In function 'int getP(int, int)':
synchronization.cpp:42:7: warning: unused variable 'a' [-Wunused-variable]
   int a = Nr[i][0], b = Nr[i][1];
       ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:89:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^
synchronization.cpp:98:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int ix; scanf("%d", &ix); ix--;
                           ^
synchronization.cpp:103:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15504 KB Output is correct
2 Correct 0 ms 15504 KB Output is correct
3 Correct 3 ms 15504 KB Output is correct
4 Correct 3 ms 15504 KB Output is correct
5 Correct 3 ms 15504 KB Output is correct
6 Correct 6 ms 15504 KB Output is correct
7 Correct 76 ms 15900 KB Output is correct
8 Correct 89 ms 15900 KB Output is correct
9 Correct 83 ms 15900 KB Output is correct
10 Correct 4886 ms 19200 KB Output is correct
11 Correct 5053 ms 19200 KB Output is correct
12 Correct 1373 ms 23236 KB Output is correct
13 Correct 1183 ms 19736 KB Output is correct
14 Correct 1946 ms 19200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 21376 KB Output is correct
2 Correct 599 ms 21320 KB Output is correct
3 Correct 429 ms 23232 KB Output is correct
4 Correct 426 ms 23228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15504 KB Output is correct
2 Correct 0 ms 15504 KB Output is correct
3 Correct 0 ms 15504 KB Output is correct
4 Correct 3 ms 15504 KB Output is correct
5 Correct 0 ms 15504 KB Output is correct
6 Correct 6 ms 15504 KB Output is correct
7 Correct 59 ms 16244 KB Output is correct
8 Correct 1603 ms 23236 KB Output is correct
9 Correct 1596 ms 23236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1523 ms 23232 KB Output is correct
2 Correct 456 ms 23204 KB Output is correct
3 Correct 456 ms 23232 KB Output is correct
4 Correct 423 ms 23236 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15504 KB Output is correct
2 Correct 0 ms 15504 KB Output is correct
3 Correct 0 ms 15504 KB Output is correct
4 Correct 0 ms 15504 KB Output is correct
5 Correct 3 ms 15504 KB Output is correct
6 Correct 86 ms 15900 KB Output is correct
7 Correct 5309 ms 19200 KB Output is correct
8 Correct 1539 ms 23236 KB Output is correct
9 Correct 1136 ms 19736 KB Output is correct
10 Correct 2389 ms 19200 KB Output is correct
11 Correct 706 ms 21376 KB Output is correct
12 Correct 713 ms 21372 KB Output is correct
13 Correct 413 ms 23236 KB Output is correct