Submission #1072026

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

incursion

#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
using namespace std;
const int N=5e4+5;
int n,par[N],dp[N],a[N],sz[N];
vector<int> adj1[N],adj2[N];
bool vis[N];
void dfs1(int x,int p){
	for (auto u:adj1[x]){
		if (u==p) continue;
		dfs1(u,x);
		dp[x]|=dp[u];
	}return;
}
void dfs2(int x,int p){
	par[x]=p;
	sz[x]=1;
	for (auto u:adj2[x]){
		if (u==p) continue;
		dfs2(u,x);
		sz[x]+=sz[u];
	}return;
}
bool cmp(int x,int y){
	return sz[x]>sz[y];
}
void dfs3(int x,int p){
	if (!a[x]){
		a[par[x]]=visit(par[x]);
		dfs3(par[x],x);
		return;
	}
	for (auto u:adj2[x]){
		if (u==par[x] || u==p) continue;
		a[u]=visit(u);
		if (a[u]==0) visit(x);
		else{
			dfs3(u,x);
			break;
		}
	}
	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);
	}
	dp[safe]=1;
	int r;
	for (int i=1;i<=n;i++) if (adj1[i].size()==2) r=i;
	dfs1(r,0);
	vector<int> v;
	for (int i=1;i<=n;i++) v.pb(dp[i]);
	return v;
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
	n=F.size()+1;
	a[curr]=t;
	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()==2) r=i;
	dfs2(r,0);
	for (int i=1;i<=n;i++) sort(adj2[i].begin(),adj2[i].end(),cmp);
	dfs3(curr,0);
	return;
}

Compilation message (stderr)

incursion.cpp: In function 'std::vector<int> mark(std::vector<std::pair<int, int> >, int)':
incursion.cpp:54:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |  dfs1(r,0);
      |  ~~~~^~~~~
incursion.cpp: In function 'void locate(std::vector<std::pair<int, int> >, int, int)':
incursion.cpp:68:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  dfs2(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: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40