oj.uz

Submission #25482

# Submission time Handle Problem Language Result Execution time Memory
25482 2017-06-22T11:29:41 Z kajebiii Synchronization (JOI13_synchronization) C++14
50 / 100
 8000 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 = 300; // 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
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 0 ms 15504 KB Output is correct
4 Correct 0 ms 15504 KB Output is correct
5 Correct 0 ms 15504 KB Output is correct
6 Correct 3 ms 15504 KB Output is correct
7 Correct 69 ms 15900 KB Output is correct
8 Correct 76 ms 15900 KB Output is correct
9 Correct 66 ms 15900 KB Output is correct
10 Correct 7866 ms 19200 KB Output is correct
11 Execution timed out 8000 ms 19200 KB Execution timed out
12 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 21376 KB Output is correct
2 Correct 816 ms 21320 KB Output is correct
3 Correct 583 ms 23232 KB Output is correct
4 Correct 576 ms 23232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15504 KB Output is correct
2 Correct 3 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 3 ms 15504 KB Output is correct
7 Correct 46 ms 16244 KB Output is correct
8 Correct 1879 ms 23236 KB Output is correct
9 Correct 1793 ms 23232 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2099 ms 23232 KB Output is correct
2 Correct 716 ms 23204 KB Output is correct
3 Correct 739 ms 23232 KB Output is correct
4 Correct 776 ms 23232 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15504 KB Output is correct
2 Correct 3 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 6 ms 15504 KB Output is correct
6 Correct 73 ms 15900 KB Output is correct
7 Execution timed out 8000 ms 19200 KB Execution timed out
8 Halted 0 ms 0 KB -