oj.uz

Submission #467124

# Submission time Handle Problem Language Result Execution time Memory
467124 2021-08-21T18:30:06 Z AriaH Synchronization (JOI13_synchronization) C++11
100 / 100
 599 ms 27520 KB 
/** 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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5132 KB Output is correct
5 Correct 3 ms 5196 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 17 ms 6732 KB Output is correct
8 Correct 17 ms 6804 KB Output is correct
9 Correct 18 ms 6748 KB Output is correct
10 Correct 288 ms 22084 KB Output is correct
11 Correct 304 ms 21956 KB Output is correct
12 Correct 513 ms 26592 KB Output is correct
13 Correct 129 ms 21916 KB Output is correct
14 Correct 202 ms 20972 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 23884 KB Output is correct
2 Correct 101 ms 23552 KB Output is correct
3 Correct 122 ms 25596 KB Output is correct
4 Correct 123 ms 25664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5128 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 26 ms 7316 KB Output is correct
8 Correct 592 ms 27356 KB Output is correct
9 Correct 599 ms 27436 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 27332 KB Output is correct
2 Correct 221 ms 26736 KB Output is correct
3 Correct 199 ms 26820 KB Output is correct
4 Correct 196 ms 26876 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 5 ms 5352 KB Output is correct
6 Correct 28 ms 6872 KB Output is correct
7 Correct 361 ms 22868 KB Output is correct
8 Correct 521 ms 27520 KB Output is correct
9 Correct 159 ms 22944 KB Output is correct
10 Correct 215 ms 22208 KB Output is correct
11 Correct 156 ms 25044 KB Output is correct
12 Correct 143 ms 24972 KB Output is correct
13 Correct 210 ms 26820 KB Output is correct