Submission #228130

#	Time	Username	Problem	Language	Result	Execution time	Memory
228130		arnold518	Synchronization (JOI13_synchronization)	C++14	100 / 100	590 ms	85292 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXM = 1e5;

int N, M, Q, P[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
vector<int> adj[MAXN+10];

int A[MAXN+10], B[MAXN+10];
int S[MAXN+10], E[MAXN+10], idx[MAXN+10], cnt;

void dfs(int now, int bef)
{
	S[now]=++cnt;
	idx[cnt]=now;
	for(auto &nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now);
	}
	E[now]=cnt;
}

struct priority_set
{
	priority_queue<int> PQ1, PQ2;
	void push(int x) { PQ1.push(x); }
	void pop(int x) { PQ2.push(x); }
	int top()
	{
		while(!PQ1.empty() && !PQ2.empty() && PQ1.top()==PQ2.top()) PQ1.pop(), PQ2.pop();
		if(PQ1.empty()) return -1;
		return PQ1.top();
	}
};

priority_set tree[MAXN*4+10];

void update1(int node, int tl, int tr, int l, int r, int v)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].push(v);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, v);
	update1(node*2+1, mid+1, tr, l, r, v);
}

void update2(int node, int tl, int tr, int l, int r, int v)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].pop(v);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, l, r, v);
	update2(node*2+1, mid+1, tr, l, r, v);
}

int query(int node, int tl, int tr, int p)
{
	if(tl==tr) return tree[node].top();
	int mid=tl+tr>>1;
	if(p<=mid) return max(query(node*2, tl, mid, p), tree[node].top());
	else return max(query(node*2+1, mid+1, tr, p), tree[node].top());
}

void push(int x) { update1(1, 1, N, S[x], E[x], S[x]); }
void pop(int x) { update2(1, 1, N, S[x], E[x], S[x]); }
int query(int x) { return idx[query(1, 1, N, S[x])]; }

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<N; i++)
	{
		scanf("%d%d", &X[i], &Y[i]);
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	dfs(1, 0);
	for(i=1; i<=N; i++) push(i), A[i]=1;
	for(i=1; i<N; i++) if(S[X[i]]<S[Y[i]]) swap(X[i], Y[i]);

	while(M--)
	{
		int e;
		scanf("%d", &e);
		if(P[e]==0)
		{
			int v=query(Y[e]), u=X[e];
			A[v]+=A[u]-B[e];
			pop(X[e]);
		}
		else
		{
			int v=query(Y[e]), u=X[e];
			B[e]=A[v];
			A[u]=A[v];
			push(X[e]);
		}
		P[e]^=1;
	}
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		printf("%d\n", A[query(t)]);
	}
}

Compilation message (stderr)

synchronization.cpp: In function 'void update1(int, int, int, int, int, int)':
synchronization.cpp:53:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
synchronization.cpp: In function 'void update2(int, int, int, int, int, int)':
synchronization.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
synchronization.cpp: In function 'int query(int, int, int, int)':
synchronization.cpp:74:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:85:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
synchronization.cpp:87:7: 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:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &X[i], &Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &e);
   ~~~~~^~~~~~~~~~
synchronization.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~

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