oj.uz

Submission #557958

# Submission time Handle Problem Language Result Execution time Memory
557958 2022-05-06T11:07:13 Z AdamGS Inside information (BOI21_servers) C++17
100 / 100
 627 ms 37192 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=12e4+7, INF=1e9+7;
vector<pair<int,int>>V[LIM];
vector<int>S;
int typ[LIM], A[LIM], B[LIM], czas[LIM], usun[LIM], ile[LIM], ans[LIM];
int rosnie[LIM], maleje[LIM], najw[LIM], najm[LIM], oc[LIM], ktory[LIM];
int cent(int x, int o, int n) {
	S.pb(x);
	ile[x]=1;
	int p=-1, ma=0;
	for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
		int t=cent(i.nd, x, n);
		if(t!=-1) p=t;
		ile[x]+=ile[i.nd];
		ma=max(ma, ile[i.nd]);
	}
	ma=max(ma, n-ile[x]);
	if(ma<=n/2) p=x;
	return p;
}
void DFS(int x, int o, int lst) {
	for(auto i : V[x]) if(!usun[i.nd] && i.nd!=o) {
		oc[i.nd]=oc[x];
		rosnie[i.nd]=rosnie[x];
		maleje[i.nd]=maleje[x];
		najw[i.nd]=najw[x];
		najm[i.nd]=najm[x];
		if(lst && i.st<lst) rosnie[i.nd]=0;
		if(lst && i.st>lst) maleje[i.nd]=0;
		if(lst) {
			najw[i.nd]=max(najw[i.nd], i.st);
			najm[i.nd]=min(najm[i.nd], i.st);
		}
		DFS(i.nd, x, i.st);
	}
}
void cd(int x, int n, vector<int>pyt) {
	x=cent(x, x, n);
	S.clear();
	cent(x, x, n);
	usun[x]=rosnie[x]=maleje[x]=1;
	najm[x]=INF;
	najw[x]=-INF;
	rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
		ktory[V[x][i].nd]=i;
		oc[V[x][i].nd]=V[x][i].nd;
		rosnie[V[x][i].nd]=maleje[V[x][i].nd]=1;
		najw[V[x][i].nd]=najm[V[x][i].nd]=V[x][i].st;
		DFS(V[x][i].nd, x, V[x][i].st);
	}
	vector<int>P[V[x].size()], Q, C;
	for(auto i : pyt) {
		if(typ[i]) {
			C.pb(i);
			if(A[i]!=x) P[ktory[oc[A[i]]]].pb(i);
		} else {
			if(oc[A[i]]==oc[B[i]] && A[i]!=x && B[i]!=x) P[ktory[oc[A[i]]]].pb(i);
			else Q.pb(i);
		}
	}
	for(auto i : Q) {
		if(A[i]==x && maleje[B[i]] && najw[B[i]]<=czas[i]) ans[i]=1;
		if(B[i]==x && rosnie[A[i]] && najw[A[i]]<=czas[i]) ans[i]=1;
		if(rosnie[A[i]] && maleje[B[i]] && najm[A[i]]>najw[B[i]]) 
			if(max(najw[A[i]], najw[B[i]])<=czas[i]) ans[i]=1;
	}
	vector<pair<int,int>>T;
	for(auto i : S) if(i!=x && rosnie[i]) T.pb({najw[i], -ktory[oc[i]]-1});
	for(auto i : C) if(maleje[A[i]]) {
		if(najw[A[i]]<=czas[i]) ++ans[i];
		T.pb({czas[i], i});
	}
	int N=1;
	while(N<V[x].size()) N*=2;
	vector<int>tr(2*N);
	sort(all(T));
	for(auto i : T) {
		if(i.nd<0) {
			i.nd*=-1; --i.nd;
			i.nd+=N;
			while(i.nd) {
				++tr[i.nd];
				i.nd/=2;
			}
		} else {
			int l=ktory[oc[A[i.nd]]]+1, r=V[x].size()-1;
			if(A[i.nd]==x) l=0;
			if(l>r) continue;
			l+=N; r+=N;
			ans[i.nd]+=tr[l];
			if(l!=r) ans[i.nd]+=tr[r];
			while(l/2!=r/2) {
				if(l%2==0) ans[i.nd]+=tr[l+1];
				if(r%2==1) ans[i.nd]+=tr[r-1];
				l/=2; r/=2;
			}
		}
	}
	rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k, ilen=0, ilek=0;
	cin >> n >> k;
	rep(i, n+k-1) {
		char c;
		cin >> c;
		if(c=='S') {
			++ilen;
			int a, b;
			cin >> a >> b; --a; --b;
			V[a].pb({ilen, b});
			V[b].pb({ilen, a});
		} else if(c=='Q') {
			cin >> A[ilek] >> B[ilek]; 
			--A[ilek]; --B[ilek]; czas[ilek]=ilen;
			++ilek;
		} else {
			cin >> A[ilek]; --A[ilek];
			czas[ilek]=ilen; typ[ilek]=1;
			++ilek;
		}
	}
	rep(i, n) sort(all(V[i]));
	vector<int>T;
	rep(i, k) T.pb(i);
	cd(0, n, T);
	rep(i, k) if(typ[i]) cout << ans[i] << '\n'; else cout << (ans[i]?"yes":"no") << '\n';
}

Compilation message

servers.cpp: In function 'void cd(int, int, std::vector<int>)':
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
servers.cpp:52:2: note: in expansion of macro 'rep'
   52 |  rep(i, V[x].size()) if(!usun[V[x][i].nd]) {
      |  ^~~
servers.cpp:82:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  while(N<V[x].size()) N*=2;
      |        ~^~~~~~~~~~~~
servers.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
servers.cpp:107:2: note: in expansion of macro 'rep'
  107 |  rep(i, V[x].size()) if(!usun[V[x][i].nd]) cd(V[x][i].nd, ile[V[x][i].nd], P[i]);
      |  ^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6736 KB Output is correct
2 Correct 34 ms 6916 KB Output is correct
3 Correct 34 ms 7728 KB Output is correct
4 Correct 36 ms 7028 KB Output is correct
5 Correct 35 ms 7436 KB Output is correct
6 Correct 38 ms 6992 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6736 KB Output is correct
2 Correct 34 ms 6916 KB Output is correct
3 Correct 34 ms 7728 KB Output is correct
4 Correct 36 ms 7028 KB Output is correct
5 Correct 35 ms 7436 KB Output is correct
6 Correct 38 ms 6992 KB Output is correct
7 Correct 37 ms 7212 KB Output is correct
8 Correct 51 ms 8440 KB Output is correct
9 Correct 53 ms 9140 KB Output is correct
10 Correct 58 ms 8852 KB Output is correct
11 Correct 60 ms 8780 KB Output is correct
12 Correct 39 ms 8732 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6600 KB Output is correct
2 Correct 106 ms 21448 KB Output is correct
3 Correct 110 ms 21444 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6600 KB Output is correct
2 Correct 106 ms 21448 KB Output is correct
3 Correct 110 ms 21444 KB Output is correct
4 Correct 32 ms 6752 KB Output is correct
5 Correct 110 ms 24160 KB Output is correct
6 Correct 112 ms 23196 KB Output is correct
7 Correct 140 ms 25172 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6824 KB Output is correct
2 Correct 336 ms 25076 KB Output is correct
3 Correct 359 ms 25084 KB Output is correct
4 Correct 186 ms 26536 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6824 KB Output is correct
2 Correct 336 ms 25076 KB Output is correct
3 Correct 359 ms 25084 KB Output is correct
4 Correct 186 ms 26536 KB Output is correct
5 Correct 38 ms 7116 KB Output is correct
6 Correct 398 ms 28960 KB Output is correct
7 Correct 260 ms 31272 KB Output is correct
8 Correct 427 ms 29100 KB Output is correct
9 Correct 360 ms 29124 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6852 KB Output is correct
2 Correct 217 ms 17308 KB Output is correct
3 Correct 336 ms 16952 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6852 KB Output is correct
2 Correct 217 ms 17308 KB Output is correct
3 Correct 336 ms 16952 KB Output is correct
4 Correct 26 ms 7112 KB Output is correct
5 Correct 271 ms 21684 KB Output is correct
6 Correct 366 ms 20832 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6796 KB Output is correct
2 Correct 368 ms 25032 KB Output is correct
3 Correct 336 ms 25132 KB Output is correct
4 Correct 201 ms 26496 KB Output is correct
5 Correct 25 ms 6856 KB Output is correct
6 Correct 209 ms 17236 KB Output is correct
7 Correct 360 ms 16932 KB Output is correct
8 Correct 267 ms 16580 KB Output is correct
9 Correct 343 ms 17232 KB Output is correct
10 Correct 361 ms 22004 KB Output is correct
11 Correct 372 ms 21084 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6796 KB Output is correct
2 Correct 368 ms 25032 KB Output is correct
3 Correct 336 ms 25132 KB Output is correct
4 Correct 201 ms 26496 KB Output is correct
5 Correct 25 ms 6856 KB Output is correct
6 Correct 209 ms 17236 KB Output is correct
7 Correct 360 ms 16932 KB Output is correct
8 Correct 267 ms 16580 KB Output is correct
9 Correct 343 ms 17232 KB Output is correct
10 Correct 361 ms 22004 KB Output is correct
11 Correct 372 ms 21084 KB Output is correct
12 Correct 27 ms 7080 KB Output is correct
13 Correct 420 ms 29040 KB Output is correct
14 Correct 266 ms 31160 KB Output is correct
15 Correct 398 ms 29176 KB Output is correct
16 Correct 414 ms 29160 KB Output is correct
17 Correct 29 ms 7892 KB Output is correct
18 Correct 270 ms 21636 KB Output is correct
19 Correct 347 ms 20704 KB Output is correct
20 Correct 371 ms 21160 KB Output is correct
21 Correct 373 ms 21468 KB Output is correct
22 Correct 468 ms 26200 KB Output is correct
23 Correct 627 ms 25728 KB Output is correct
24 Correct 502 ms 24788 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6736 KB Output is correct
2 Correct 33 ms 6936 KB Output is correct
3 Correct 35 ms 7724 KB Output is correct
4 Correct 36 ms 6988 KB Output is correct
5 Correct 47 ms 7508 KB Output is correct
6 Correct 30 ms 6928 KB Output is correct
7 Correct 26 ms 6592 KB Output is correct
8 Correct 102 ms 21348 KB Output is correct
9 Correct 102 ms 21548 KB Output is correct
10 Correct 26 ms 6708 KB Output is correct
11 Correct 372 ms 25116 KB Output is correct
12 Correct 349 ms 25028 KB Output is correct
13 Correct 188 ms 26484 KB Output is correct
14 Correct 33 ms 6844 KB Output is correct
15 Correct 214 ms 17348 KB Output is correct
16 Correct 292 ms 16860 KB Output is correct
17 Correct 282 ms 16636 KB Output is correct
18 Correct 321 ms 17208 KB Output is correct
19 Correct 366 ms 22028 KB Output is correct
20 Correct 328 ms 21044 KB Output is correct
21 Correct 145 ms 21232 KB Output is correct
22 Correct 143 ms 19924 KB Output is correct
23 Correct 197 ms 17104 KB Output is correct
24 Correct 209 ms 16892 KB Output is correct
25 Correct 378 ms 21940 KB Output is correct
26 Correct 349 ms 16072 KB Output is correct
27 Correct 303 ms 16032 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6736 KB Output is correct
2 Correct 33 ms 6936 KB Output is correct
3 Correct 35 ms 7724 KB Output is correct
4 Correct 36 ms 6988 KB Output is correct
5 Correct 47 ms 7508 KB Output is correct
6 Correct 30 ms 6928 KB Output is correct
7 Correct 26 ms 6592 KB Output is correct
8 Correct 102 ms 21348 KB Output is correct
9 Correct 102 ms 21548 KB Output is correct
10 Correct 26 ms 6708 KB Output is correct
11 Correct 372 ms 25116 KB Output is correct
12 Correct 349 ms 25028 KB Output is correct
13 Correct 188 ms 26484 KB Output is correct
14 Correct 33 ms 6844 KB Output is correct
15 Correct 214 ms 17348 KB Output is correct
16 Correct 292 ms 16860 KB Output is correct
17 Correct 282 ms 16636 KB Output is correct
18 Correct 321 ms 17208 KB Output is correct
19 Correct 366 ms 22028 KB Output is correct
20 Correct 328 ms 21044 KB Output is correct
21 Correct 145 ms 21232 KB Output is correct
22 Correct 143 ms 19924 KB Output is correct
23 Correct 197 ms 17104 KB Output is correct
24 Correct 209 ms 16892 KB Output is correct
25 Correct 378 ms 21940 KB Output is correct
26 Correct 349 ms 16072 KB Output is correct
27 Correct 303 ms 16032 KB Output is correct
28 Correct 27 ms 7208 KB Output is correct
29 Correct 57 ms 9560 KB Output is correct
30 Correct 54 ms 10236 KB Output is correct
31 Correct 65 ms 9908 KB Output is correct
32 Correct 63 ms 9984 KB Output is correct
33 Correct 43 ms 9732 KB Output is correct
34 Correct 27 ms 7760 KB Output is correct
35 Correct 110 ms 24156 KB Output is correct
36 Correct 133 ms 23188 KB Output is correct
37 Correct 130 ms 25180 KB Output is correct
38 Correct 27 ms 8012 KB Output is correct
39 Correct 415 ms 29012 KB Output is correct
40 Correct 270 ms 31160 KB Output is correct
41 Correct 408 ms 29048 KB Output is correct
42 Correct 401 ms 29144 KB Output is correct
43 Correct 30 ms 8016 KB Output is correct
44 Correct 275 ms 21728 KB Output is correct
45 Correct 337 ms 20636 KB Output is correct
46 Correct 353 ms 21172 KB Output is correct
47 Correct 379 ms 21452 KB Output is correct
48 Correct 474 ms 26452 KB Output is correct
49 Correct 547 ms 25800 KB Output is correct
50 Correct 568 ms 24952 KB Output is correct
51 Correct 137 ms 26556 KB Output is correct
52 Correct 133 ms 25792 KB Output is correct
53 Correct 124 ms 25148 KB Output is correct
54 Correct 124 ms 24372 KB Output is correct
55 Correct 121 ms 27680 KB Output is correct
56 Correct 234 ms 23208 KB Output is correct
57 Correct 355 ms 37192 KB Output is correct
58 Correct 430 ms 21060 KB Output is correct
59 Correct 295 ms 20176 KB Output is correct