Submission #467124

#	Time	Username	Problem	Language	Result	Execution time	Memory
467124		AriaH	Synchronization (JOI13_synchronization)	C++11	100 / 100	599 ms	27520 KiB

synchronization

/** Alone at the top **/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

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

#define F				first
#define S				second
#define all(x)				x.begin(), x.end()
#define SZ(x)				(int)x.size()
#define Mp				make_pair

const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }

int n, m, q, ptr, St[N], Fi[N], fir[N], sec[N], H[N], in[N], Ans[N], Last[N], fen[N], P[LOG][N];

vector < int > G[N];

inline void add(int i, int x) { for(i += 3; i < N; i += i & -i) { fen[i] += x; } }

inline int ask(int i, int ret = 0)
{
	for(i += 3; i; i -= i & -i) { ret += fen[i]; }
	return ret;
}

void pre(int v)
{
	St[v] = ++ptr;
	H[v] = H[P[0][v]] + 1;
	for(int T = 1; T < LOG; T ++)
	{
		P[T][v] = P[T - 1][P[T - 1][v]];
	}
	for(auto u : G[v])
	{
		if(u == P[0][v]) continue;
		P[0][u] = v;
		pre(u);
	}
	Fi[v] = ptr;
}

inline int jad(int v)
{
	for(int T = LOG - 1; ~T; T --)
	{
		if(!P[T][v] || ask(St[v]) ^ ask(St[P[T][v]])) continue;
		v = P[T][v];
	}
	return v;
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i < n; i ++)
	{
		scanf("%d%d", &fir[i], &sec[i]);
		G[fir[i]].push_back(sec[i]);
		G[sec[i]].push_back(fir[i]);
	}
	pre(1);
	for(int i = 1; i <= n; i ++)
	{
		Ans[i] = 1;
		add(St[i], 1);
		add(Fi[i] + 1, -1);
	}
	for(int i = 1; i < n; i ++) { if(H[fir[i]] < H[sec[i]]) swap(fir[i], sec[i]); }
	for(int j = 1; j <= m; j ++)
	{
		int id;
		scanf("%d", &id);
		///printf("here j = %d\n", j);
		int v = fir[id], u = sec[id];
		if(in[id])
		{
			Last[id] = Ans[v] = Ans[jad(v)];
			add(St[v], 1);
			add(Fi[v] + 1, -1);
		}
		else
		{
			Ans[jad(u)] += Ans[v] - Last[id];
			add(St[v], -1);
			add(Fi[v] + 1, 1);
		}
		in[id] ^= 1;
		/*for(int i = 1; i <= n; i ++)
		{
			printf("i = %d yal : %d\n", i, ask(St[i]));
		}
		for(int i = 1; i <= n; i ++)
		{
			printf("v = %d Ans = %d jad : %d\n", i, Ans[i], jad(i));
		}
		*/
	}
	while(q --)
	{
		int node;
		scanf("%d", &node);
		printf("%d\n", Ans[jad(node)]);
	}
	return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d", &fir[i], &sec[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d", &id);
      |   ~~~~~^~~~~~~~~~~
synchronization.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d", &node);
      |   ~~~~~^~~~~~~~~~~~~

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