oj.uz

Submission #228130

# Submission time Handle Problem Language Result Execution time Memory
228130 2020-04-30T03:08:10 Z arnold518 Synchronization (JOI13_synchronization) C++14
100 / 100
 590 ms 85292 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55168 KB Output is correct
2 Correct 32 ms 55168 KB Output is correct
3 Correct 31 ms 55256 KB Output is correct
4 Correct 32 ms 55168 KB Output is correct
5 Correct 33 ms 55168 KB Output is correct
6 Correct 33 ms 55288 KB Output is correct
7 Correct 55 ms 56824 KB Output is correct
8 Correct 55 ms 56704 KB Output is correct
9 Correct 56 ms 56696 KB Output is correct
10 Correct 446 ms 71608 KB Output is correct
11 Correct 460 ms 71544 KB Output is correct
12 Correct 506 ms 84332 KB Output is correct
13 Correct 259 ms 69616 KB Output is correct
14 Correct 286 ms 70648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 79212 KB Output is correct
2 Correct 253 ms 78444 KB Output is correct
3 Correct 260 ms 79956 KB Output is correct
4 Correct 260 ms 79988 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55160 KB Output is correct
2 Correct 31 ms 55168 KB Output is correct
3 Correct 33 ms 55160 KB Output is correct
4 Correct 34 ms 55168 KB Output is correct
5 Correct 32 ms 55168 KB Output is correct
6 Correct 34 ms 55416 KB Output is correct
7 Correct 60 ms 57976 KB Output is correct
8 Correct 559 ms 85096 KB Output is correct
9 Correct 590 ms 85216 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 85292 KB Output is correct
2 Correct 304 ms 80884 KB Output is correct
3 Correct 303 ms 81012 KB Output is correct
4 Correct 314 ms 81396 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 55168 KB Output is correct
2 Correct 32 ms 55168 KB Output is correct
3 Correct 33 ms 55168 KB Output is correct
4 Correct 32 ms 55168 KB Output is correct
5 Correct 35 ms 55296 KB Output is correct
6 Correct 61 ms 56828 KB Output is correct
7 Correct 542 ms 72288 KB Output is correct
8 Correct 565 ms 85192 KB Output is correct
9 Correct 301 ms 70640 KB Output is correct
10 Correct 381 ms 72056 KB Output is correct
11 Correct 317 ms 80364 KB Output is correct
12 Correct 326 ms 80428 KB Output is correct
13 Correct 310 ms 81268 KB Output is correct