oj.uz

Submission #790441

# Submission time Handle Problem Language Result Execution time Memory
790441 2023-07-22T16:37:07 Z fabijan_cikac Inside information (BOI21_servers) C++17
100 / 100
 387 ms 51184 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pp pair<int, int>
#define ppp pair<int, pp>
#define F first
#define S second
#define pb push_back
 
struct Q{
	char ch; int x, y;
};
 
struct edge{
	int y, w;
};
 
const int N = 2 * 120100;
 
int n, k, sol[N];
vector<edge> v[N]; vector<Q> l;
 
int cnt[N], fen[N];
int sum(int x){
	++x; int res = 0;
	for (int i = x; i > 0; i -= i & (-i))
		res += fen[i];
	return res;
}
 
void upd(int x, int val){
	++x;
	for (int i = x; i < N; i += i & (-i))
		fen[i] += val;
}
 
int bio[N], subtree[N], par[N];
vector<int> nodes;
int dfs(int x){
	nodes.pb(x);
	bio[x] = 1; int res = 1;
	for (edge e: v[x]){
		if (!bio[e.y]){
			par[e.y] = x;
			res += dfs(e.y);
		}
	}
	subtree[x] = res; bio[x] = 0;
	return subtree[x];
}
 
int join[N], first[N], sub_idx[N], leave[N], reach[N];
int joined[N], reached[N];
void dfs2(int x, int flag, int flag2){
	bio[x] = 1; leave[x] = flag2; sub_idx[x] = flag;
	for (edge e: v[x]){
		if (!bio[e.y]){
			if (joined[x] && first[x] > e.w){
				join[e.y] = join[x];
				joined[e.y] = 1; first[e.y] = e.w;
			}
			
			if (reached[x] && reach[x] < e.w){
				reach[e.y] = e.w;
				reached[e.y] = 1;
			}
			dfs2(e.y, flag, flag2);
		}
	}
	bio[x] = 0;
}
 
int findCentroid(int x){
	bio[x] = 1;
	for (edge e: v[x]){
		if (bio[e.y]) continue;
		if (subtree[e.y] > (nodes.size() / 2)){
			int res = findCentroid(e.y);
			bio[x] = 0; return res;
		}
	}
	return x;
}
 
void solve(int root, vector<int> qQ, vector<int> qC){
	//find centroid
	nodes.clear(); dfs(root);
	int node = findCentroid(root); bio[node] = 1;
	
	//calc. join, reach & leave time for nodes
	join[node] = 0, reach[node] = 0, leave[node] = 0;
	joined[node] = 1; reached[node] = 1;
	sub_idx[node] = v[node].size();
	for (int i = 0; i < v[node].size(); ++i){
		edge e = v[node][i];
		if (!bio[e.y]){
			join[e.y] = e.w; first[e.y] = e.w;
			joined[e.y] = 1; reached[e.y] = 1;
			reach[e.y] = e.w; dfs2(e.y, i, e.w);
		}
	}
	
	//clear already used storage for pushed queryes (Q/C)
	vector<vector<int> > nqQ, nqC;
	nqQ.resize(v[node].size() + 1); nqC.resize(v[node].size() + 1);
		
	//solve/push query of type Q
	for (int idx: qQ){
		int x = l[idx].x, y = l[idx].y;
		if (x == node || y == node){
			if (x == node && y == node)
				sol[idx] = 1;
			else if (x == node){
				if (joined[y] && join[y] < idx)
					sol[idx] = 1;
			}
			else if (y == node){
				if (reached[x] && reach[x] < idx)
					sol[idx] = 1;
			}
		}
		else if (sub_idx[x] != sub_idx[y]){
			if (joined[y] && reached[x] && leave[x] > join[y] && reach[x] < idx)
				sol[idx] = 1;
		}
		else nqQ[sub_idx[x]].pb(idx);
	}
	
	//solve/push query of type C
	vector<ppp> sweep;
	for (int idx: qC)
		sweep.pb({idx, {1, -1}});
	for (int y: nodes){
		if (reached[y] && y != node)
			sweep.pb({reach[y], {0, leave[y]}});
	}
	sort(sweep.begin(), sweep.end());
	
	int all_sum = 0;
	for (ppp p: sweep){
		if (p.S.F == 0){
			++cnt[p.S.S]; upd(p.S.S, 1);
			++all_sum;
		}
		else{
			int x = l[p.F].x;
			if (x == node)
				sol[p.F] += (all_sum + 1);
			else{
				if (!joined[x]) continue;
				sol[p.F] += (all_sum - sum(join[x]));
				if (join[x] <= p.F) ++sol[p.F];
			}
		}
	}
	for (edge e: v[node]){
		if (cnt[e.w] != 0){
			upd(e.w, -cnt[e.w]); cnt[e.w] = 0;
		}
	}
	
	for (int idx: qC) nqC[sub_idx[l[idx].x]].pb(idx);
	
	//further decompose
	for (int y: nodes){
		joined[y] = 0; reached[y] = 0;
	}
	for (int i = 0; i < v[node].size(); ++i){
		edge e = v[node][i];
		if (!bio[e.y]) solve(e.y, nqQ[i], nqC[i]);
	}
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k; vector<int> qQ, qC;
	l.pb({'C', 0});
	for (int i = 1; i <= n + k - 1; ++i){
		char ch; cin >> ch;
		if (ch == 'S'){
			int x, y; cin >> x >> y;
			--x, --y; v[x].pb({y, i}), v[y].pb({x, i});
			l.pb({ch, x, y});
		}
		else if (ch == 'Q'){
			int x, y; cin >> x >> y;
			l.pb({ch, x - 1, y - 1}); qQ.pb(i);
		}
		else{
			int x; cin >> x; qC.pb(i);
			l.pb({ch, x - 1, -1});
		}
	}
	
	solve(0, qQ, qC);
	for (int i = 1; i <= n + k - 1; ++i){
		if (l[i].ch == 'Q'){
			if (sol[i])
				cout << "yes";
			else cout << "no";
			cout << '\n';
		}
		else if (l[i].ch == 'C')
			cout << sol[i] << '\n';
	}
	
	return 0;
}

Compilation message

servers.cpp: In function 'int findCentroid(int)':
servers.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   if (subtree[e.y] > (nodes.size() / 2)){
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void solve(int, std::vector<int>, std::vector<int>)':
servers.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (int i = 0; i < v[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
servers.cpp:169:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (int i = 0; i < v[node].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10752 KB Output is correct
2 Correct 27 ms 12108 KB Output is correct
3 Correct 39 ms 13188 KB Output is correct
4 Correct 30 ms 12220 KB Output is correct
5 Correct 29 ms 11768 KB Output is correct
6 Correct 26 ms 11668 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10752 KB Output is correct
2 Correct 27 ms 12108 KB Output is correct
3 Correct 39 ms 13188 KB Output is correct
4 Correct 30 ms 12220 KB Output is correct
5 Correct 29 ms 11768 KB Output is correct
6 Correct 26 ms 11668 KB Output is correct
7 Correct 23 ms 11200 KB Output is correct
8 Correct 44 ms 14032 KB Output is correct
9 Correct 37 ms 14332 KB Output is correct
10 Correct 59 ms 14248 KB Output is correct
11 Correct 83 ms 13440 KB Output is correct
12 Correct 32 ms 12500 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10676 KB Output is correct
2 Correct 104 ms 33992 KB Output is correct
3 Correct 91 ms 34064 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10676 KB Output is correct
2 Correct 104 ms 33992 KB Output is correct
3 Correct 91 ms 34064 KB Output is correct
4 Correct 23 ms 10888 KB Output is correct
5 Correct 96 ms 35668 KB Output is correct
6 Correct 98 ms 35764 KB Output is correct
7 Correct 103 ms 35948 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10984 KB Output is correct
2 Correct 238 ms 34256 KB Output is correct
3 Correct 209 ms 34260 KB Output is correct
4 Correct 151 ms 35744 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10984 KB Output is correct
2 Correct 238 ms 34256 KB Output is correct
3 Correct 209 ms 34260 KB Output is correct
4 Correct 151 ms 35744 KB Output is correct
5 Correct 24 ms 11412 KB Output is correct
6 Correct 261 ms 35272 KB Output is correct
7 Correct 221 ms 36788 KB Output is correct
8 Correct 319 ms 36360 KB Output is correct
9 Correct 309 ms 36400 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11032 KB Output is correct
2 Correct 150 ms 28440 KB Output is correct
3 Correct 174 ms 27700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11032 KB Output is correct
2 Correct 150 ms 28440 KB Output is correct
3 Correct 174 ms 27700 KB Output is correct
4 Correct 23 ms 11144 KB Output is correct
5 Correct 212 ms 29832 KB Output is correct
6 Correct 244 ms 28860 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10988 KB Output is correct
2 Correct 216 ms 34212 KB Output is correct
3 Correct 242 ms 34288 KB Output is correct
4 Correct 170 ms 35804 KB Output is correct
5 Correct 21 ms 11016 KB Output is correct
6 Correct 143 ms 28508 KB Output is correct
7 Correct 176 ms 27740 KB Output is correct
8 Correct 170 ms 26436 KB Output is correct
9 Correct 216 ms 28216 KB Output is correct
10 Correct 240 ms 32856 KB Output is correct
11 Correct 214 ms 31008 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10988 KB Output is correct
2 Correct 216 ms 34212 KB Output is correct
3 Correct 242 ms 34288 KB Output is correct
4 Correct 170 ms 35804 KB Output is correct
5 Correct 21 ms 11016 KB Output is correct
6 Correct 143 ms 28508 KB Output is correct
7 Correct 176 ms 27740 KB Output is correct
8 Correct 170 ms 26436 KB Output is correct
9 Correct 216 ms 28216 KB Output is correct
10 Correct 240 ms 32856 KB Output is correct
11 Correct 214 ms 31008 KB Output is correct
12 Correct 24 ms 11400 KB Output is correct
13 Correct 272 ms 35280 KB Output is correct
14 Correct 216 ms 36804 KB Output is correct
15 Correct 309 ms 36388 KB Output is correct
16 Correct 322 ms 36412 KB Output is correct
17 Correct 23 ms 11152 KB Output is correct
18 Correct 246 ms 29796 KB Output is correct
19 Correct 262 ms 28848 KB Output is correct
20 Correct 247 ms 28432 KB Output is correct
21 Correct 278 ms 29636 KB Output is correct
22 Correct 318 ms 34316 KB Output is correct
23 Correct 356 ms 32796 KB Output is correct
24 Correct 313 ms 31860 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10800 KB Output is correct
2 Correct 27 ms 12112 KB Output is correct
3 Correct 31 ms 13328 KB Output is correct
4 Correct 30 ms 12344 KB Output is correct
5 Correct 36 ms 11688 KB Output is correct
6 Correct 26 ms 11664 KB Output is correct
7 Correct 20 ms 10652 KB Output is correct
8 Correct 90 ms 33984 KB Output is correct
9 Correct 84 ms 34028 KB Output is correct
10 Correct 27 ms 11008 KB Output is correct
11 Correct 230 ms 34296 KB Output is correct
12 Correct 214 ms 34296 KB Output is correct
13 Correct 143 ms 35868 KB Output is correct
14 Correct 21 ms 11000 KB Output is correct
15 Correct 144 ms 28532 KB Output is correct
16 Correct 190 ms 27684 KB Output is correct
17 Correct 246 ms 26520 KB Output is correct
18 Correct 190 ms 28200 KB Output is correct
19 Correct 207 ms 32876 KB Output is correct
20 Correct 195 ms 31000 KB Output is correct
21 Correct 98 ms 35196 KB Output is correct
22 Correct 94 ms 32008 KB Output is correct
23 Correct 137 ms 28228 KB Output is correct
24 Correct 148 ms 28208 KB Output is correct
25 Correct 246 ms 34392 KB Output is correct
26 Correct 181 ms 26952 KB Output is correct
27 Correct 179 ms 27112 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10800 KB Output is correct
2 Correct 27 ms 12112 KB Output is correct
3 Correct 31 ms 13328 KB Output is correct
4 Correct 30 ms 12344 KB Output is correct
5 Correct 36 ms 11688 KB Output is correct
6 Correct 26 ms 11664 KB Output is correct
7 Correct 20 ms 10652 KB Output is correct
8 Correct 90 ms 33984 KB Output is correct
9 Correct 84 ms 34028 KB Output is correct
10 Correct 27 ms 11008 KB Output is correct
11 Correct 230 ms 34296 KB Output is correct
12 Correct 214 ms 34296 KB Output is correct
13 Correct 143 ms 35868 KB Output is correct
14 Correct 21 ms 11000 KB Output is correct
15 Correct 144 ms 28532 KB Output is correct
16 Correct 190 ms 27684 KB Output is correct
17 Correct 246 ms 26520 KB Output is correct
18 Correct 190 ms 28200 KB Output is correct
19 Correct 207 ms 32876 KB Output is correct
20 Correct 195 ms 31000 KB Output is correct
21 Correct 98 ms 35196 KB Output is correct
22 Correct 94 ms 32008 KB Output is correct
23 Correct 137 ms 28228 KB Output is correct
24 Correct 148 ms 28208 KB Output is correct
25 Correct 246 ms 34392 KB Output is correct
26 Correct 181 ms 26952 KB Output is correct
27 Correct 179 ms 27112 KB Output is correct
28 Correct 23 ms 11264 KB Output is correct
29 Correct 45 ms 14052 KB Output is correct
30 Correct 37 ms 14360 KB Output is correct
31 Correct 58 ms 14296 KB Output is correct
32 Correct 81 ms 13528 KB Output is correct
33 Correct 31 ms 12396 KB Output is correct
34 Correct 23 ms 10864 KB Output is correct
35 Correct 106 ms 35692 KB Output is correct
36 Correct 98 ms 35700 KB Output is correct
37 Correct 99 ms 35976 KB Output is correct
38 Correct 24 ms 11416 KB Output is correct
39 Correct 261 ms 35320 KB Output is correct
40 Correct 219 ms 36756 KB Output is correct
41 Correct 306 ms 36448 KB Output is correct
42 Correct 308 ms 36388 KB Output is correct
43 Correct 22 ms 11208 KB Output is correct
44 Correct 218 ms 29884 KB Output is correct
45 Correct 246 ms 28912 KB Output is correct
46 Correct 264 ms 28432 KB Output is correct
47 Correct 280 ms 29588 KB Output is correct
48 Correct 387 ms 34384 KB Output is correct
49 Correct 365 ms 32712 KB Output is correct
50 Correct 297 ms 31804 KB Output is correct
51 Correct 110 ms 37260 KB Output is correct
52 Correct 104 ms 36644 KB Output is correct
53 Correct 131 ms 36432 KB Output is correct
54 Correct 100 ms 36956 KB Output is correct
55 Correct 101 ms 38412 KB Output is correct
56 Correct 155 ms 32248 KB Output is correct
57 Correct 304 ms 51184 KB Output is correct
58 Correct 294 ms 29188 KB Output is correct
59 Correct 188 ms 27188 KB Output is correct