oj.uz

답안 #25454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25454 2017-06-22T07:58:28 Z khsoo01 동기화 (JOI13_synchronization) C++11
60 / 100
 216 ms 45004 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 34664 KB Output is correct
2 Correct 0 ms 34664 KB Output is correct
3 Correct 0 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 34796 KB Output is correct
7 Correct 9 ms 35456 KB Output is correct
8 Correct 23 ms 35324 KB Output is correct
9 Correct 16 ms 35456 KB Output is correct
10 Correct 153 ms 41792 KB Output is correct
11 Correct 169 ms 41792 KB Output is correct
12 Correct 109 ms 43708 KB Output is correct
13 Correct 106 ms 42196 KB Output is correct
14 Correct 156 ms 41528 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 44672 KB Output is correct
2 Correct 93 ms 43560 KB Output is correct
3 Correct 66 ms 45004 KB Output is correct
4 Correct 49 ms 44396 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 34664 KB Output is correct
2 Correct 3 ms 34664 KB Output is correct
3 Correct 3 ms 34664 KB Output is correct
4 Correct 6 ms 34664 KB Output is correct
5 Correct 3 ms 34664 KB Output is correct
6 Correct 6 ms 34664 KB Output is correct
7 Correct 9 ms 34664 KB Output is correct
8 Correct 216 ms 34664 KB Output is correct
9 Correct 209 ms 34664 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 34664 KB Output is correct
2 Correct 156 ms 34664 KB Output is correct
3 Correct 146 ms 34664 KB Output is correct
4 Correct 126 ms 34664 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 34664 KB Output isn't correct
2 Halted 0 ms 0 KB -