oj.uz

Submission #25430

# Submission time Handle Problem Language Result Execution time Memory
25430 2017-06-22T06:56:07 Z 김동현(#1064) Synchronization (JOI13_synchronization) C++14
60 / 100
 443 ms 21700 KB 
#include <bits/stdc++.h>
using namespace std;

struct E{
	int x, i;
};

struct Inf{
	int t, x;
	bool operator<(const Inf &oth) const {
		return (t == oth.t) ? (x < oth.x) : (t > oth.t);
	}
};

int n, m, q, ch[200010], c[100010];
vector<E> e[100010];
vector<int> tv[100010];
set<int> ss;

int f1(int x, int p, int t){
	int ret = 1;
	for(auto &i : e[x]){
		if(i.x == p) continue;
		int lt = (int)(upper_bound(tv[i.i].begin(), tv[i.i].end(), t) - tv[i.i].begin() - 1);
		if(lt < 0) continue;
		int nt;
		if(lt & 1) nt = tv[i.i][lt] - 1;
		else nt = t;
		ret += f1(i.x, x, nt);
	}
	return ret;
}

const int sz = 131072, inf = 1e9;
struct Seg{
	int mx[2 * sz], mn[2 * sz], iv[2];
	void ini(){
		iv[0] = inf; iv[1] = -inf;
		fill(mx + 1, mx + 2 * sz, -inf);
		fill(mn + 1, mn + 2 * sz, inf);
		for(int i = 1; i <= n; i++) mx[i + sz] = mn[i + sz] = i;
	}
	void upd(int t, int s, int e, int x){
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1){
				if(t) mx[s] = max(mx[s], x);
				else mn[s] = min(mn[s], x);
				s++;
			}
			if(e % 2 == 0){
				if(t) mx[e] = max(mx[e], x);
				else mn[e] = min(mn[e], x);
				e--;
			}
		}
	}
	int get(int t, int x){
		int ret = iv[t];
		for(x += sz; x; x /= 2) ret = (t ? max(ret, mx[x]) : min(ret, mn[x]));
		return ret;
	}
	int ans(int x){
		return get(1, x) - get(0, x) + 1;
	}
} S;

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1, x, y; i <= n - 1; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for(int i = 1; i <= m; i++){
		scanf("%d", ch + i);
		tv[ch[i]].push_back(i);
	}
	if(q == 1){
		scanf("%d", &q);
		printf("%d\n", f1(q, 0, m + 1));
	}
	else{
		for(int i = 0; i <= n; i++) ss.insert(i);
		S.ini();
		for(int i = 1; i <= m; i++){
			c[ch[i]]++;
			if(c[ch[i]] & 1){
				ss.erase(ch[i]);
				auto it = ss.upper_bound(ch[i]); it--;
				int ls = (*it) + 1;
				int re = *(ss.lower_bound(ch[i]));
				S.upd(1, ls, re, max(S.get(1, ls), S.get(1, re)));
				S.upd(0, ls, re, min(S.get(0, ls), S.get(0, re)));
			}
			else{
				ss.insert(ch[i]);
			}
		}
		for(int x; q--; ){
			scanf("%d", &x);
			printf("%d\n", S.ans(x));
		}
		return 0;
	}
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:68:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
                             ^
synchronization.cpp:70:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
synchronization.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", ch + i);
                      ^
synchronization.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &q);
                  ^
synchronization.cpp:100:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9932 KB Output is correct
2 Correct 0 ms 9932 KB Output is correct
3 Correct 0 ms 9932 KB Output is correct
4 Correct 3 ms 9932 KB Output is correct
5 Correct 0 ms 9932 KB Output is correct
6 Correct 0 ms 10064 KB Output is correct
7 Correct 9 ms 10592 KB Output is correct
8 Correct 6 ms 10592 KB Output is correct
9 Correct 9 ms 10592 KB Output is correct
10 Correct 189 ms 16400 KB Output is correct
11 Correct 169 ms 16532 KB Output is correct
12 Correct 106 ms 15872 KB Output is correct
13 Correct 119 ms 16936 KB Output is correct
14 Correct 159 ms 16796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 20228 KB Output is correct
2 Correct 49 ms 18728 KB Output is correct
3 Correct 56 ms 21700 KB Output is correct
4 Correct 56 ms 20884 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9932 KB Output is correct
2 Correct 0 ms 9932 KB Output is correct
3 Correct 3 ms 9932 KB Output is correct
4 Correct 0 ms 9932 KB Output is correct
5 Correct 0 ms 9932 KB Output is correct
6 Correct 3 ms 10064 KB Output is correct
7 Correct 33 ms 10988 KB Output is correct
8 Correct 443 ms 20492 KB Output is correct
9 Correct 416 ms 20492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 20492 KB Output is correct
2 Correct 196 ms 20756 KB Output is correct
3 Correct 203 ms 20888 KB Output is correct
4 Correct 193 ms 20888 KB Output is correct

Subtask #5
0 / 40.0

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