Submission #1068681

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068681	2024-08-21T11:20:52 Z	Abito	Toy Train (IOI17_train)	C++17	11 / 100	722 ms	1960 KB

train

#include "train.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int N=5005;
int n,vis[N],par[N],sz[N];
bool a[N],c[N],cyc[N],h,self[N];
vector<int> adj[2][N],t;
void dfs0(int x){
	vis[x]=1;
	for (auto u:adj[0][x]){
		if (vis[u]) continue;
		dfs0(u);
	}t.pb(x);
	return;
}
int getpar(int x){
	if (par[x]==x) return x;
	return par[x]=getpar(par[x]);
}
void link(int x,int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return;
	if (sz[x]>sz[y]) swap(x,y);
	sz[y]+=sz[x];
	par[x]=y;
	return;
}
void dfs1(int x,int p){
	vis[x]=1;
	link(x,p);
	for (auto u:adj[1][x]) if (!vis[u]) dfs1(u,p);
	return;
}
bool getans(int s){
	queue<int> q;
	q.push(s);
	vis[s]=1;
	bool ok=0;
	while (!q.empty()){
		int x=q.front();
		//cout<<x<<' ';
		q.pop();
		if (c[x]){
			if (sz[getpar(x)]>1) ok=1;
			if (self[x]==1) ok=1;
		}
		for (auto u:adj[0][x]){
			if (vis[u]) continue;
			else{
				vis[u]=1;
				q.push(u);
			}
		}
	}//cout<<endl;
	return ok;
}
std::vector<int32_t> who_wins(std::vector<int32_t> A, std::vector<int32_t> r, std::vector<int32_t> u, std::vector<int32_t> v) {
	n=A.size();
	for (int i=1;i<=n;i++) a[i]=A[i-1],c[i]=r[i-1],par[i]=i,sz[i]=1;
	for (int i=0;i<u.size();i++){
		adj[0][u[i]+1].pb(v[i]+1);
		adj[1][v[i]+1].pb(u[i]+1);
		if (u[i]==v[i]) self[u[i]+1]=1;
	}
	vector<int> ans(n);
	for (int i=1;i<=n;i++){
		if (vis[i]) continue;
		dfs0(i);
	}
	memset(vis,0,sizeof(vis));
	reverse(t.begin(),t.end());
	for (auto u:t) if (!vis[u]) dfs1(u,u);
	memset(vis,0,sizeof(vis));
	for (int i=1;i<=n;i++){
		ans[i-1]=getans(i);
		memset(vis,0,sizeof(vis));
	}
	return ans;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i=0;i<u.size();i++){
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	155 ms	1372 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	600 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	105 ms	1792 KB	Output is correct
2	Correct	95 ms	1624 KB	Output is correct
3	Correct	90 ms	1624 KB	Output is correct
4	Correct	722 ms	1628 KB	Output is correct
5	Correct	505 ms	1908 KB	Output is correct
6	Correct	348 ms	1716 KB	Output is correct
7	Correct	413 ms	1812 KB	Output is correct
8	Correct	221 ms	1628 KB	Output is correct
9	Correct	194 ms	1628 KB	Output is correct
10	Correct	279 ms	1880 KB	Output is correct
11	Correct	251 ms	1752 KB	Output is correct
12	Correct	20 ms	1624 KB	Output is correct
13	Correct	633 ms	1960 KB	Output is correct
14	Correct	659 ms	1880 KB	Output is correct
15	Correct	659 ms	1880 KB	Output is correct
16	Correct	640 ms	1884 KB	Output is correct
17	Correct	634 ms	1884 KB	Output is correct
18	Correct	148 ms	1372 KB	Output is correct