Submission #25463

#	Time	Username	Problem	Language	Result	Execution time	Memory
25463		zigui	Synchronization (JOI13_synchronization)	C++14	0 / 100	249 ms	24636 KiB

synchronization

#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 200005;
const int MM = 1000000007;

int st[MX], fin[MX], state[MX];
pii E[MX];
vector<pii> tmp[MX];
vector<t3> G[MX];
int a, b, c;

int vst[MX], cnt[MX], ans[MX];

int get_cnt(int x, int p){
	if( vst[x] ) return cnt[x] = 0;
	cnt[x] = 1;
	for(t3 c : G[x]){
		if( get<2>(c) == p ) continue;
		cnt[x] += get_cnt(get<2>(c), x);
	}
	return cnt[x];
}

void get_pair(int x, int s, int e, int p, vector<t3> &R){
//	if( vst[x] ) return;
	R.emplace_back(s, e, x); 
	for(t3 t : G[x]){
		tie(a, b, c) = t;
		if( c == p ) continue;
		if( e < a ) continue;
		get_pair(c, max(s, a), min(e, b), x, R);
	}
}

struct BIT{
	int t[MX];
	void update(int x, int v){
		while(x < MX) t[x] += v, x += x&-x;
	}
	int read(int x){
		int r = 0;
		while(x) r += t[x], x -= x&-x;
		return r;
	}
} tree;

void get_answer(vector<t3> &Q, int type){
	sort(Q.begin(), Q.end());
	reverse(Q.begin(), Q.end());
	
	vector<int> L;
	for(t3 e : Q){
		tie(a, b, c) = e;
		L.push_back(a);
	}
	sort(L.begin(), L.end());
	for(t3 e : Q){
		tie(a, b, c) = e;
		int t = 0;
		ans[c] += (t = lower_bound(L.begin(), L.end(), b) - L.begin()) * type;
//		printf("add : %d, %d\n", c, t*type);
	}
}

void solve(int x){
	get_cnt(x, -1);

	int r = x;
	while(G[r].size()){
		int mx = 0;
		for(t3 c : G[r]) if( cnt[mx] < cnt[get<2>(c)] ) mx = get<2>(c);
		if( cnt[mx]*2 <= cnt[r] ) break;
		cnt[r] -= cnt[mx]; cnt[mx] += cnt[r]; r = mx;
	}
//	printf("%d\n", r);

	vector<t3> Q, R;
	for(t3 e : G[r]){
		tie(a, b, c) = e;
		get_pair(c, a, b, r, Q);
//		get_answer(Q, -1);
		for(t3 t : Q){
			int a, b, c;
			tie(a, b, c) = t;
//			printf("%d %d %d\n", a, b, c);
			R.push_back(t);
		}
//		printf("\n");
		Q.clear();
	}
	ans[r] += R.size() + 1;
//	get_answer(R, 1);
	for(t3 t : R){
		tie(a, b, c) = t;
//		ans[c]++;
	}
	
	vst[r] = 1;
	for(t3 e : G[x]){
		int c = get<2>(e);
		if( !vst[c] ) solve(c);
	}
}

int main()
{
	int N, M, Q;
	scanf("%d%d%d", &N, &M, &Q);
	for(int i = 1; i < N; i++){
		scanf("%d%d", &a, &b); E[i] = pii(a, b);
		tmp[a].emplace_back(i, b);
		tmp[b].emplace_back(i, a);
	}
	for(int i = 1; i <= M; i++){
		scanf("%d", &a);
		if( state[a] ) fin[a] = i;
		else if( !st[a] ) st[a] = i;
		state[a] ^= 1;
	}

	for(int i = 1; i < N; i++) if(state[i]) fin[i] = M+1;
	for(int i = 1; i <= N; i++){
		for(pii c : tmp[i]){
			int a = c.second, b = i;
			if( fin[c.first] != 0 && a != b ){
				G[b].emplace_back(st[c.first], fin[c.first], a);
//				printf("%d -> %d, %d~%d\n", b, a, st[c.first], fin[c.first]);
			}
		}
	}

	for(int i = 1; i <= N; i++){
		if( vst[i] == 0 ) solve(i);
	}
	for(int i = 1; i <= Q; i++){
		scanf("%d", &a);
		printf("%d\n", ans[a]);
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:130:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &Q);
                             ^
synchronization.cpp:132:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b); E[i] = pii(a, b);
                        ^
synchronization.cpp:137:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^
synchronization.cpp:158:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40