oj.uz

Submission #557946

# Submission time Handle Problem Language Result Execution time Memory
557946 2022-05-06T10:35:51 Z AdamGS Inside information (BOI21_servers) C++17
50 / 100
 391 ms 28960 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) {
	S.clear();
	x=cent(x, x, n);
	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;
	}
	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: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:75:2: note: in expansion of macro 'rep'
   75 |  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 24 ms 6748 KB Output is correct
2 Correct 35 ms 6944 KB Output is correct
3 Correct 37 ms 7636 KB Output is correct
4 Correct 46 ms 6968 KB Output is correct
5 Correct 40 ms 7388 KB Output is correct
6 Correct 29 ms 6996 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6748 KB Output is correct
2 Correct 35 ms 6944 KB Output is correct
3 Correct 37 ms 7636 KB Output is correct
4 Correct 46 ms 6968 KB Output is correct
5 Correct 40 ms 7388 KB Output is correct
6 Correct 29 ms 6996 KB Output is correct
7 Incorrect 25 ms 7028 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6512 KB Output is correct
2 Correct 109 ms 19084 KB Output is correct
3 Correct 117 ms 19064 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6512 KB Output is correct
2 Correct 109 ms 19084 KB Output is correct
3 Correct 117 ms 19064 KB Output is correct
4 Incorrect 25 ms 6760 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6728 KB Output is correct
2 Correct 334 ms 25300 KB Output is correct
3 Correct 354 ms 25284 KB Output is correct
4 Correct 157 ms 27716 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6728 KB Output is correct
2 Correct 334 ms 25300 KB Output is correct
3 Correct 354 ms 25284 KB Output is correct
4 Correct 157 ms 27716 KB Output is correct
5 Incorrect 28 ms 7884 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6792 KB Output is correct
2 Correct 154 ms 17172 KB Output is correct
3 Correct 354 ms 20420 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6792 KB Output is correct
2 Correct 154 ms 17172 KB Output is correct
3 Correct 354 ms 20420 KB Output is correct
4 Incorrect 32 ms 7796 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6740 KB Output is correct
2 Correct 354 ms 25300 KB Output is correct
3 Correct 364 ms 25276 KB Output is correct
4 Correct 176 ms 27680 KB Output is correct
5 Correct 26 ms 7736 KB Output is correct
6 Correct 180 ms 19772 KB Output is correct
7 Correct 257 ms 20460 KB Output is correct
8 Correct 315 ms 20224 KB Output is correct
9 Correct 317 ms 20924 KB Output is correct
10 Correct 391 ms 25460 KB Output is correct
11 Correct 296 ms 24644 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6740 KB Output is correct
2 Correct 354 ms 25300 KB Output is correct
3 Correct 364 ms 25276 KB Output is correct
4 Correct 176 ms 27680 KB Output is correct
5 Correct 26 ms 7736 KB Output is correct
6 Correct 180 ms 19772 KB Output is correct
7 Correct 257 ms 20460 KB Output is correct
8 Correct 315 ms 20224 KB Output is correct
9 Correct 317 ms 20924 KB Output is correct
10 Correct 391 ms 25460 KB Output is correct
11 Correct 296 ms 24644 KB Output is correct
12 Incorrect 29 ms 7960 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6736 KB Output is correct
2 Correct 46 ms 6916 KB Output is correct
3 Correct 35 ms 7840 KB Output is correct
4 Correct 34 ms 6960 KB Output is correct
5 Correct 38 ms 7328 KB Output is correct
6 Correct 32 ms 7004 KB Output is correct
7 Correct 25 ms 6528 KB Output is correct
8 Correct 94 ms 20892 KB Output is correct
9 Correct 107 ms 22036 KB Output is correct
10 Correct 25 ms 7608 KB Output is correct
11 Correct 358 ms 28640 KB Output is correct
12 Correct 351 ms 28716 KB Output is correct
13 Correct 162 ms 28960 KB Output is correct
14 Correct 27 ms 7708 KB Output is correct
15 Correct 171 ms 19796 KB Output is correct
16 Correct 293 ms 20520 KB Output is correct
17 Correct 275 ms 20336 KB Output is correct
18 Correct 339 ms 20868 KB Output is correct
19 Correct 339 ms 25636 KB Output is correct
20 Correct 326 ms 24648 KB Output is correct
21 Correct 100 ms 22724 KB Output is correct
22 Correct 120 ms 21592 KB Output is correct
23 Correct 201 ms 20428 KB Output is correct
24 Correct 194 ms 20544 KB Output is correct
25 Correct 350 ms 24812 KB Output is correct
26 Correct 322 ms 19904 KB Output is correct
27 Correct 312 ms 20120 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6736 KB Output is correct
2 Correct 46 ms 6916 KB Output is correct
3 Correct 35 ms 7840 KB Output is correct
4 Correct 34 ms 6960 KB Output is correct
5 Correct 38 ms 7328 KB Output is correct
6 Correct 32 ms 7004 KB Output is correct
7 Correct 25 ms 6528 KB Output is correct
8 Correct 94 ms 20892 KB Output is correct
9 Correct 107 ms 22036 KB Output is correct
10 Correct 25 ms 7608 KB Output is correct
11 Correct 358 ms 28640 KB Output is correct
12 Correct 351 ms 28716 KB Output is correct
13 Correct 162 ms 28960 KB Output is correct
14 Correct 27 ms 7708 KB Output is correct
15 Correct 171 ms 19796 KB Output is correct
16 Correct 293 ms 20520 KB Output is correct
17 Correct 275 ms 20336 KB Output is correct
18 Correct 339 ms 20868 KB Output is correct
19 Correct 339 ms 25636 KB Output is correct
20 Correct 326 ms 24648 KB Output is correct
21 Correct 100 ms 22724 KB Output is correct
22 Correct 120 ms 21592 KB Output is correct
23 Correct 201 ms 20428 KB Output is correct
24 Correct 194 ms 20544 KB Output is correct
25 Correct 350 ms 24812 KB Output is correct
26 Correct 322 ms 19904 KB Output is correct
27 Correct 312 ms 20120 KB Output is correct
28 Incorrect 29 ms 7948 KB Extra information in the output file
29 Halted 0 ms 0 KB -