제출 #1072283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072283		Abito	The Ties That Guide Us (CEOI23_incursion)	C++17	30 / 100	251 ms	15096 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
#define elif else if
using namespace std;
const int N=5e4+5;
int n;
vector<int> adj1[N],a,b,adj2[N];
bool c[N],d[N];
void geta(int x,int p){
	a.pb(x);
	for (auto u:adj1[x]){
		if (u==p) continue;
		geta(u,x);
	}return;
}
void getb(int x,int p){
	b.pb(x);
	for (auto u:adj2[x]){
		if (u==p) continue;
		getb(u,x);
	}return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
	n=F.size()+1;
	if (n==2){
		if (safe==1) return {0,1};
		return {1,0};
	}
	for (auto u:F){
		adj1[u.first].pb(u.second);
		adj1[u.second].pb(u.first);
	}
	int r;
	for (int i=1;i<=n;i++) if (adj1[i].size()==1) r=i;
	a.pb(0);
	geta(r,0);
	for (int i=1;i<=n;i++) c[i]=1;
	if (n&1){
		int j;
		for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
		if (j<=n/2+1) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
		else for (int i=n/2+1;i<=j;i++) c[a[i]]=0;
		vector<int> v;
		for (int i=1;i<=n;i++) v.pb(c[i]);
		return v;
	}
	else{
		int j;
		for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
		if (j==n/2 || j==n/2+1){
			c[safe]=0;	
		}
		elif (j<n/2) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
		else for (int i=n/2;i<=j;i++) c[a[i]]=0;
		vector<int> v;
		for (int i=1;i<=n;i++) v.pb(c[i]);
		return v;
	}
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	if (n==2){
		if (t==0) return;
		if (curr==1) visit(2);
		else visit(1);
		return;
	}
	for (auto u:F){
		adj2[u.first].pb(u.second);
		adj2[u.second].pb(u.first);
	}
   int r;
	for (int i=1;i<=n;i++) if (adj2[i].size()==1) r=i;
	b.pb(0);
	getb(r,0);
	//for (auto u:b) cout<<u<<' ';
	//cout<<endl;
	if (n&1){
		int j;
		for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
		d[curr]=t;
		while (true){
			if (d[b[j]]){
				if (j<n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
				}
				else{
					j--;
					d[b[j]]=visit(b[j]);
				}
			}
			else{
				//return;
				if (j==1 || j==n) return;
				if (j<n/2+1){
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j++;
						visit(b[j]);
						return;
					}
					continue;
				}
				elif (j>n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j--;
						visit(b[j]);
						return;
					}
					continue;
				}
				j--;
				d[b[j]]=visit(b[j]);
				if (!d[b[j]]) continue;
				j++;
				d[b[j]]=visit(b[j]);
				j++;
				d[b[j]]=visit(b[j]);
				if (!d[b[j]]) continue;
				j--;d[b[j]]=visit(b[j]);
				return;
			}
		}
	}
	else{
		int j;
		for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
		d[curr]=t;
		while (true){
			if (d[b[j]]){
				if (j<=n/2){
					j++;
					d[b[j]]=visit(b[j]);
				}
				else{
					j--;
					d[b[j]]=visit(b[j]);
				}
			}
			else{
				if (j==1 || j==n) return;
				if (j<n/2){
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j++;
						visit(b[j]);
						return;
					}
					continue;
				}
				if (j>n/2+1){
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[j]]){
						j--;
						visit(b[j]);
						return;
					}
					continue;
				}
				if (j==n/2){
					j--;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					if (d[b[n/2+1]]){
						j--;
						d[b[j]]=visit(b[j]);
						j--;
						d[b[j]]=visit(b[j]);
						return;
					}
					if (!d[b[n/2+2]]) continue;
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					continue;
				}
				else{
					j++;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					j--;
					d[b[j]]=visit(b[j]);
					if (d[b[n/2]]){
						j++;
						d[b[j]]=visit(b[j]);
						j++;
						d[b[j]]=visit(b[j]);
						return;
					}
					if (!d[b[n/2-1]]) continue;
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					j++;
					d[b[j]]=visit(b[j]);
					continue;
				}
			}
		}
		return;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:135:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |    if (d[b[j]]){
      |             ^
incursion.cpp:84:13: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |    if (d[b[j]]){
      |             ^
incursion.cpp:76:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |  getb(r,0);
      |  ~~~~^~~~~
incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:43:26: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |   else for (int i=n/2+1;i<=j;i++) c[a[i]]=0;
      |                         ~^~~
incursion.cpp:37:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |  geta(r,0);
      |  ~~~~^~~~~
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
• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40