oj.uz

Submission #25444

# Submission time Handle Problem Language Result Execution time Memory
25444 2017-06-22T07:37:28 Z 김현수(#1065) Synchronization (JOI13_synchronization) C++11
30 / 100
 166 ms 31112 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

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];

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() {}

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:41: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 'int main()':
synchronization.cpp:70: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:72: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:74: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 20768 KB Output is correct
2 Correct 6 ms 20768 KB Output is correct
3 Correct 0 ms 20768 KB Output is correct
4 Correct 3 ms 20768 KB Output is correct
5 Correct 6 ms 20768 KB Output is correct
6 Correct 0 ms 20900 KB Output is correct
7 Correct 16 ms 21560 KB Output is correct
8 Correct 13 ms 21428 KB Output is correct
9 Correct 16 ms 21560 KB Output is correct
10 Correct 166 ms 27896 KB Output is correct
11 Correct 166 ms 27896 KB Output is correct
12 Correct 93 ms 29812 KB Output is correct
13 Correct 83 ms 28300 KB Output is correct
14 Correct 119 ms 27632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 30776 KB Output is correct
2 Correct 89 ms 29664 KB Output is correct
3 Correct 66 ms 31112 KB Output is correct
4 Correct 63 ms 30500 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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