oj.uz

답안 #1081431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1081431 2024-08-30T04:48:52 Z LCJLY The Ties That Guide Us (CEOI23_incursion) C++17
0 / 100
 227 ms 15236 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]<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]>=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]<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]<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]>=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

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 2820 KB Partially correct

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 227 ms 13828 KB Partially correct
2 Partially correct 208 ms 14684 KB Partially correct
3 Partially correct 112 ms 14720 KB Partially correct
4 Partially correct 99 ms 13980 KB Partially correct
5 Partially correct 186 ms 14596 KB Partially correct
6 Partially correct 81 ms 13220 KB Partially correct
7 Partially correct 80 ms 12448 KB Partially correct
8 Partially correct 199 ms 14068 KB Partially correct
9 Partially correct 203 ms 15236 KB Partially correct
10 Partially correct 166 ms 13700 KB Partially correct
11 Partially correct 90 ms 14480 KB Partially correct
12 Incorrect 227 ms 13704 KB Not correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 82 ms 8316 KB Partially correct
2 Partially correct 70 ms 8612 KB Partially correct
3 Incorrect 75 ms 8304 KB Not correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2 ms 2820 KB Partially correct
2 Partially correct 227 ms 13828 KB Partially correct
3 Partially correct 208 ms 14684 KB Partially correct
4 Partially correct 112 ms 14720 KB Partially correct
5 Partially correct 99 ms 13980 KB Partially correct
6 Partially correct 186 ms 14596 KB Partially correct
7 Partially correct 81 ms 13220 KB Partially correct
8 Partially correct 80 ms 12448 KB Partially correct
9 Partially correct 199 ms 14068 KB Partially correct
10 Partially correct 203 ms 15236 KB Partially correct
11 Partially correct 166 ms 13700 KB Partially correct
12 Partially correct 90 ms 14480 KB Partially correct
13 Incorrect 227 ms 13704 KB Not correct
14 Halted 0 ms 0 KB -