oj.uz

Submission #1081443

# Submission time Handle Problem Language Result Execution time Memory
1081443 2024-08-30T04:57:52 Z LCJLY The Ties That Guide Us (CEOI23_incursion) C++17
12 / 100
 267 ms 15496 KB 
#include "incursion.h"
#include <bits/stdc++.h>
//#include "sample_grader.cpp"
using namespace std;

//#define int long long 
//#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;

int n;
vector<int>adj[45005];
int sz[45005];
int pp[45005];
int child[45005];

void dfs(int index, int par){
	sz[index]=1;
	for(auto it:adj[index]){
		if(it==par) continue;
		dfs(it,index);
		pp[it]=index;
		child[index]=it;
		sz[index]+=sz[it];
	}
}

vector<int>mark(vector<pair<int, int>> F, int safe){
	n=F.size()+1;
	for(int x=0;x<n-1;x++){
		adj[F[x].first].push_back(F[x].second);
		adj[F[x].second].push_back(F[x].first);
	}
	
	dfs(safe,-1);
	
	vector<int>ans(n);
	for(int x=1;x<=n;x++){
		if(x==safe){
			ans[x-1]=2;
		}
		else if(sz[x]-1<n-sz[x]){
			ans[x-1]=0;
		}		
		else ans[x-1]=1;
	}
	return ans;
}


//visit()
void locate(vector<pair<int, int>> F, int curr, int t){
	n=F.size()+1;
	for(int x=0;x<=n;x++){
		adj[x].clear();
		sz[x]=0;
	}
	for(int x=0;x<n-1;x++){
		adj[F[x].first].push_back(F[x].second);
		adj[F[x].second].push_back(F[x].first);
	}
	
	for(int x=1;x<=n;x++){
		if(adj[x].size()==1){
			dfs(x,-1);
			break;
		}
	}
	int cur=curr;
	
	//potentially start at centroid
	int take=-1;
	for(int i=0;i<2;i++){
		if(t==2){
			return;
		}
		else if(t==1){
			//go to smaller side
			if(sz[cur]-1>=n-sz[cur]){
				t=visit(pp[cur]);
				take=cur;
				cur=pp[cur];
			}
			else{
				t=visit(child[cur]);
				take=cur;
				cur=child[cur];
			}
		}
		else{
			if(sz[cur]-1<n-sz[cur]){
				t=visit(pp[cur]);
				take=cur;
				cur=pp[cur];
			}
			else{
				t=visit(child[cur]);
				take=cur;
				cur=child[cur];
			}
		}
	}

	while(t!=2){
		if(t==0){
			//go to larger one
			if(pp[cur]!=take&&sz[cur]-1<n-sz[cur]){
				t=visit(pp[cur]);
				take=cur;
				cur=pp[cur];
			}
			else{
				t=visit(child[cur]);
				take=cur;
				cur=child[cur];
			}
		}
		else if(t==1){
			//go to smaller one
			if(pp[cur]!=take&&sz[cur]-1>=n-sz[cur]){
				t=visit(pp[cur]);
				take=cur;
				cur=pp[cur];
			}
			else{
				t=visit(child[cur]);
				take=cur;
				cur=child[cur];
			}
		}
	}
}

Compilation message

interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         int l = (numbers.size() == N ? N : 0);
      |                  ~~~~~~~~~~~~~~~^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2828 KB Partially correct

Subtask #1
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 197 ms 15364 KB Partially correct
2 Partially correct 202 ms 15412 KB Partially correct
3 Partially correct 115 ms 15412 KB Partially correct
4 Partially correct 96 ms 14484 KB Partially correct
5 Partially correct 202 ms 14604 KB Partially correct
6 Partially correct 74 ms 13412 KB Partially correct
7 Partially correct 86 ms 13412 KB Partially correct
8 Partially correct 206 ms 15496 KB Partially correct
9 Partially correct 221 ms 15408 KB Partially correct
10 Partially correct 141 ms 14368 KB Partially correct
11 Partially correct 99 ms 14632 KB Partially correct
12 Partially correct 265 ms 14892 KB Partially correct
13 Partially correct 75 ms 13444 KB Partially correct
14 Partially correct 77 ms 13408 KB Partially correct
15 Partially correct 200 ms 15400 KB Partially correct
16 Partially correct 218 ms 15416 KB Partially correct
17 Partially correct 113 ms 14716 KB Partially correct
18 Partially correct 106 ms 14688 KB Partially correct
19 Partially correct 168 ms 14096 KB Partially correct
20 Partially correct 89 ms 13596 KB Partially correct
21 Partially correct 92 ms 13504 KB Partially correct
22 Partially correct 247 ms 15268 KB Partially correct
23 Partially correct 211 ms 15404 KB Partially correct
24 Partially correct 110 ms 14124 KB Partially correct
25 Partially correct 78 ms 14968 KB Partially correct
26 Partially correct 77 ms 14160 KB Partially correct
27 Partially correct 90 ms 13432 KB Partially correct
28 Partially correct 84 ms 13428 KB Partially correct
29 Partially correct 202 ms 15388 KB Partially correct
30 Partially correct 187 ms 15272 KB Partially correct
31 Partially correct 104 ms 13660 KB Partially correct
32 Partially correct 228 ms 15024 KB Partially correct
33 Partially correct 258 ms 14592 KB Partially correct
34 Partially correct 86 ms 13472 KB Partially correct
35 Partially correct 80 ms 13468 KB Partially correct
36 Partially correct 203 ms 15384 KB Partially correct
37 Partially correct 223 ms 15376 KB Partially correct
38 Partially correct 267 ms 14356 KB Partially correct
39 Partially correct 148 ms 15156 KB Partially correct
40 Partially correct 213 ms 15156 KB Partially correct
41 Partially correct 74 ms 13412 KB Partially correct
42 Partially correct 79 ms 13432 KB Partially correct
43 Partially correct 214 ms 15468 KB Partially correct
44 Partially correct 231 ms 15184 KB Partially correct
45 Partially correct 99 ms 14444 KB Partially correct
46 Partially correct 80 ms 14756 KB Partially correct
47 Partially correct 90 ms 14216 KB Partially correct
48 Partially correct 81 ms 13444 KB Partially correct
49 Partially correct 83 ms 13476 KB Partially correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 66 ms 8056 KB Partially correct
2 Incorrect 69 ms 8096 KB Not correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2828 KB Partially correct
2 Partially correct 197 ms 15364 KB Partially correct
3 Partially correct 202 ms 15412 KB Partially correct
4 Partially correct 115 ms 15412 KB Partially correct
5 Partially correct 96 ms 14484 KB Partially correct
6 Partially correct 202 ms 14604 KB Partially correct
7 Partially correct 74 ms 13412 KB Partially correct
8 Partially correct 86 ms 13412 KB Partially correct
9 Partially correct 206 ms 15496 KB Partially correct
10 Partially correct 221 ms 15408 KB Partially correct
11 Partially correct 141 ms 14368 KB Partially correct
12 Partially correct 99 ms 14632 KB Partially correct
13 Partially correct 265 ms 14892 KB Partially correct
14 Partially correct 75 ms 13444 KB Partially correct
15 Partially correct 77 ms 13408 KB Partially correct
16 Partially correct 200 ms 15400 KB Partially correct
17 Partially correct 218 ms 15416 KB Partially correct
18 Partially correct 113 ms 14716 KB Partially correct
19 Partially correct 106 ms 14688 KB Partially correct
20 Partially correct 168 ms 14096 KB Partially correct
21 Partially correct 89 ms 13596 KB Partially correct
22 Partially correct 92 ms 13504 KB Partially correct
23 Partially correct 247 ms 15268 KB Partially correct
24 Partially correct 211 ms 15404 KB Partially correct
25 Partially correct 110 ms 14124 KB Partially correct
26 Partially correct 78 ms 14968 KB Partially correct
27 Partially correct 77 ms 14160 KB Partially correct
28 Partially correct 90 ms 13432 KB Partially correct
29 Partially correct 84 ms 13428 KB Partially correct
30 Partially correct 202 ms 15388 KB Partially correct
31 Partially correct 187 ms 15272 KB Partially correct
32 Partially correct 104 ms 13660 KB Partially correct
33 Partially correct 228 ms 15024 KB Partially correct
34 Partially correct 258 ms 14592 KB Partially correct
35 Partially correct 86 ms 13472 KB Partially correct
36 Partially correct 80 ms 13468 KB Partially correct
37 Partially correct 203 ms 15384 KB Partially correct
38 Partially correct 223 ms 15376 KB Partially correct
39 Partially correct 267 ms 14356 KB Partially correct
40 Partially correct 148 ms 15156 KB Partially correct
41 Partially correct 213 ms 15156 KB Partially correct
42 Partially correct 74 ms 13412 KB Partially correct
43 Partially correct 79 ms 13432 KB Partially correct
44 Partially correct 214 ms 15468 KB Partially correct
45 Partially correct 231 ms 15184 KB Partially correct
46 Partially correct 99 ms 14444 KB Partially correct
47 Partially correct 80 ms 14756 KB Partially correct
48 Partially correct 90 ms 14216 KB Partially correct
49 Partially correct 81 ms 13444 KB Partially correct
50 Partially correct 83 ms 13476 KB Partially correct
51 Partially correct 66 ms 8056 KB Partially correct
52 Incorrect 69 ms 8096 KB Not correct
53 Halted 0 ms 0 KB -