oj.uz

Submission #25443

# Submission time Handle Problem Language Result Execution time Memory
25443 2017-06-22T07:36:25 Z 김현수(#1065) Synchronization (JOI13_synchronization) C++11
0 / 100
 59 ms 12188 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[100005], par[100005];
ll pos[100005], chk[100005], ans;
pll e[100005];

vector<ll> adj[100005];
vector<pll> gg[100005];

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 3 ms 11396 KB Output is correct
3 Correct 3 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11528 KB Output is correct
7 Correct 13 ms 12188 KB Output is correct
8 Correct 13 ms 12056 KB Output is correct
9 Correct 19 ms 12188 KB Output is correct
10 Incorrect 43 ms 11396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 40.0

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