Submission #954007

#	Time	Username	Problem	Language	Result	Execution time	Memory
954007		Trisanu_Das	Synchronization (JOI13_synchronization)	C++17	60 / 100	83 ms	31188 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40