oj.uz

Submission #25453

# Submission time Handle Problem Language Result Execution time Memory
25453 2017-06-22T07:57:33 Z 김현수(#1065) Synchronization (JOI13_synchronization) C++11
60 / 100
 233 ms 45008 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:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&R);
                  ^
synchronization.cpp: In function 'void solve2()':
synchronization.cpp:118:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&X);
                   ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:125:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&q);
                                ^
synchronization.cpp:127:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&e[i].X,&e[i].Y);
                                    ^
synchronization.cpp:129:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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 0 ms 34664 KB Output is correct
2 Correct 3 ms 34664 KB Output is correct
3 Correct 0 ms 34664 KB Output is correct
4 Correct 3 ms 34664 KB Output is correct
5 Correct 0 ms 34664 KB Output is correct
6 Correct 3 ms 34796 KB Output is correct
7 Correct 19 ms 35456 KB Output is correct
8 Correct 9 ms 35324 KB Output is correct
9 Correct 13 ms 35456 KB Output is correct
10 Correct 103 ms 41792 KB Output is correct
11 Correct 159 ms 41792 KB Output is correct
12 Correct 139 ms 43708 KB Output is correct
13 Correct 116 ms 42196 KB Output is correct
14 Correct 123 ms 41528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 44672 KB Output is correct
2 Correct 69 ms 43560 KB Output is correct
3 Correct 76 ms 45008 KB Output is correct
4 Correct 73 ms 44400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 34664 KB Output is correct
2 Correct 0 ms 34664 KB Output is correct
3 Correct 3 ms 34664 KB Output is correct
4 Correct 0 ms 34664 KB Output is correct
5 Correct 0 ms 34664 KB Output is correct
6 Correct 0 ms 34664 KB Output is correct
7 Correct 19 ms 34664 KB Output is correct
8 Correct 233 ms 34664 KB Output is correct
9 Correct 219 ms 34664 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 34664 KB Output is correct
2 Correct 116 ms 34664 KB Output is correct
3 Correct 133 ms 34664 KB Output is correct
4 Correct 149 ms 34664 KB Output is correct

Subtask #5
0 / 40.0

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