oj.uz

Submission #954007

# Submission time Handle Problem Language Result Execution time Memory
954007 2024-03-27T05:35:46 Z Trisanu_Das Synchronization (JOI13_synchronization) C++17
60 / 100
 83 ms 31188 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll mod = 1e9+7;
 
ll n, m, q, a[200005], par[200005];
ll pos[200005], chk[200005], ans;
pll e[200005];
 
vector<ll> adj[200005];
vector<pll> gg[200005];
 
struct segtree {
	ll val[444444], lim, ts;
	void init () {
		for(lim=1;lim<=n;lim<<=1);
		ts = 0;
	}
	void upd (ll S, ll E, ll X) {
		X += ++ts * mod;
		S += lim; E += lim;
		while(S<=E) {
			if(S%2==1) {val[S] = max(val[S], X); S++;}
			if(E%2==0) {val[E] = max(val[E], X); E--;}
			S>>=1; E>>=1;
		}
	}
	ll get (ll P) {
		ll ret = 0; P += lim;
		while(P) {
			ret = max(ret, val[P]);
			P >>= 1;
		}
		return ret % mod;
	}
} l, r, al, ar;
 
void calc (ll C, ll P) {
	par[C] = P;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}
 
void solve (ll C, ll P) {
	if(P) {
		for(auto &T : gg[C]) {
			if(T.X <= pos[P]) {
				pos[C] = min(pos[P], T.Y);
				break;
			}
		}
	}
	if(pos[C]) ans++;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
	}
}
 
void solve1() {
	ll R;
	scanf("%lld",&R);
	for(ll i=1;i<n;i++) {
		adj[e[i].X].push_back(e[i].Y);
		adj[e[i].Y].push_back(e[i].X);
	}
	calc(R, 0);
	for(ll i=1;i<n;i++) {
		if(par[e[i].X] != e[i].Y) swap(e[i].X, e[i].Y);
	}
	for(ll i=1;i<=m;i++) {
		if(chk[a[i]]) {
			gg[e[a[i]].X].push_back({chk[a[i]], i-1});
			chk[a[i]] = 0;
		}
		else chk[a[i]] = i;
	}
	for(ll i=1;i<n;i++) {
		if(chk[i]) gg[e[i].X].push_back({chk[i], m});
		reverse(gg[e[i].X].begin(), gg[e[i].X].end());
	}
	pos[R] = m;
	solve(R, 0);
	printf("%lld\n",ans);
}
 
void solve2() {
	l.init(); r.init();
	al.init(); ar.init();
	for(ll i=1;i<=n;i++) {
		if(e[i].X > e[i].Y) swap(e[i].X, e[i].Y);
		l.upd(i, i, i); r.upd(i, i, i);
		al.upd(i, i, i); ar.upd(i, i, i);
	}
	for(ll i=1;i<=m;i++) {
		ll C = a[i], A = e[C].X;
		if(chk[C]) {
			r.upd(l.get(A), A, A);
			l.upd(A+1, r.get(A+1), A+1);
			chk[C] = 0;
		}
		else {
			ll L = l.get(A), R = r.get(A+1);
			r.upd(L, A, R);
			l.upd(A+1, R, L);
			ar.upd(L, R, max(ar.get(A), ar.get(A+1)));
			al.upd(L, R, min(al.get(A), al.get(A+1)));
			chk[C] = 1;
		}
	}
	for(ll i=1;i<=q;i++) {
		ll X;
		scanf("%lld",&X);
		printf("%lld\n",ar.get(X)-al.get(X)+1);
	}
}
 
int main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<n;i++) {
		scanf("%lld%lld",&e[i].X,&e[i].Y);
	}
	for(ll i=1;i<=m;i++) scanf("%lld",&a[i]);
	q == 1 ? solve1() : solve2();
}

Compilation message

synchronization.cpp: In function 'void solve1()':
synchronization.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%lld",&R);
      |  ~~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void solve2()':
synchronization.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%lld",&X);
      |   ~~~~~^~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%lld%lld%lld",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |   scanf("%lld%lld",&e[i].X,&e[i].Y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:129:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |  for(ll i=1;i<=m;i++) scanf("%lld",&a[i]);
      |                       ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 3 ms 16848 KB Output is correct
5 Correct 4 ms 16732 KB Output is correct
6 Correct 4 ms 16732 KB Output is correct
7 Correct 12 ms 17756 KB Output is correct
8 Correct 8 ms 18008 KB Output is correct
9 Correct 9 ms 17744 KB Output is correct
10 Correct 60 ms 28168 KB Output is correct
11 Correct 69 ms 29004 KB Output is correct
12 Correct 55 ms 30288 KB Output is correct
13 Correct 49 ms 28636 KB Output is correct
14 Correct 53 ms 27216 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 31188 KB Output is correct
2 Correct 41 ms 30024 KB Output is correct
3 Correct 38 ms 30968 KB Output is correct
4 Correct 38 ms 30292 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 4 ms 18776 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 12 ms 19548 KB Output is correct
8 Correct 78 ms 28752 KB Output is correct
9 Correct 83 ms 28724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 28684 KB Output is correct
2 Correct 72 ms 27840 KB Output is correct
3 Correct 71 ms 27728 KB Output is correct
4 Correct 72 ms 27692 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 18780 KB Output isn't correct
2 Halted 0 ms 0 KB -