oj.uz

Submission #1081435

# Submission time Handle Problem Language Result Execution time Memory
1081435 2024-08-30T04:53:46 Z LCJLY The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 232 ms 15244 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);
	}
	
	dfs(1,-1);
	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 2 ms 2816 KB Partially correct

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 216 ms 13724 KB Partially correct
2 Partially correct 216 ms 14704 KB Partially correct
3 Partially correct 119 ms 14688 KB Partially correct
4 Partially correct 104 ms 13812 KB Partially correct
5 Partially correct 216 ms 14640 KB Partially correct
6 Partially correct 80 ms 13260 KB Partially correct
7 Partially correct 80 ms 12352 KB Partially correct
8 Partially correct 221 ms 14020 KB Partially correct
9 Partially correct 209 ms 15244 KB Partially correct
10 Partially correct 146 ms 13636 KB Partially correct
11 Partially correct 98 ms 14412 KB Partially correct
12 Incorrect 232 ms 13704 KB Not correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 80 ms 8352 KB Partially correct
2 Partially correct 76 ms 8188 KB Partially correct
3 Incorrect 84 ms 8096 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2816 KB Partially correct
2 Partially correct 216 ms 13724 KB Partially correct
3 Partially correct 216 ms 14704 KB Partially correct
4 Partially correct 119 ms 14688 KB Partially correct
5 Partially correct 104 ms 13812 KB Partially correct
6 Partially correct 216 ms 14640 KB Partially correct
7 Partially correct 80 ms 13260 KB Partially correct
8 Partially correct 80 ms 12352 KB Partially correct
9 Partially correct 221 ms 14020 KB Partially correct
10 Partially correct 209 ms 15244 KB Partially correct
11 Partially correct 146 ms 13636 KB Partially correct
12 Partially correct 98 ms 14412 KB Partially correct
13 Incorrect 232 ms 13704 KB Not correct
14 Halted 0 ms 0 KB -