Submission #1071983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071983		Abito	The Ties That Guide Us (CEOI23_incursion)	C++17	30 / 100	293 ms	15136 KiB

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
using namespace std;
const int N=5e4+5;
int dis1[N],dis2[N],n,sz[N];
vector<int> adj2[N],adj1[N];
bool found;
void dfs1(int x,int p){
	for (auto u:adj1[x]){
		if (u==p) continue;
		dis1[u]=dis1[x]+1;
		dfs1(u,x);
	}return;
}
void getsz(int x,int p){
	sz[x]=1;
	for (auto u:adj2[x]){
		if (u==p) continue;
		getsz(u,x);
		sz[x]+=sz[u];
	}
	return;
}
bool cmp(int x,int y){
	return sz[x]>sz[y];
}
void dfs2(int x,int p){
	//cout<<x<<' '<<p<<endl;
	if (dis2[x]==0){
		found=1;
		return;
	}
	for (auto u:adj2[x]){
		if (u==p) continue;
		dis2[u]=visit(u);
		if (dis2[u]==0){
			found=1;
			return;
		}
		if (dis2[u]>dis2[x]) visit(x);
		else{
			dfs2(u,x);
			return;
		}
	}
	return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
	n=F.size()+1;
	for (auto u:F){
		adj1[u.first].pb(u.second);
		adj1[u.second].pb(u.first);
	}
	dfs1(safe,0);
	vector<int> v;
	for (int i=1;i<=n;i++) v.pb(dis1[i]);
	return v;
}

void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	dis2[curr]=t;
	for (auto u:F){
		adj2[u.first].pb(u.second);
		adj2[u.second].pb(u.first);
	}
	getsz(curr,0);
	for (int i=1;i<=n;i++) sort(adj2[i].begin(),adj2[i].end(),cmp);
	dfs2(curr,0);
	return;
}

Compilation message (stderr)

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: 9 / 30
• Subtask 2: 9 / 30
• Subtask 3: 12 / 40