oj.uz

Submission #778489

# Submission time Handle Problem Language Result Execution time Memory
778489 2023-07-10T11:10:00 Z I_Love_EliskaM_ Toy Train (IOI17_train) C++14
16 / 100
 789 ms 2460 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define ll long long

vector<int> p1(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> s(n);
	vector<int> f(n);
	vector<int> ans(n);
	forn(i,m) if (u[i]==v[i]) s[u[i]]=1;
	forn(i,m) if (u[i]!=v[i]) f[u[i]]=1;
	int now=0;
	for (int i=n-1; i>=0; --i) {
		if (s[i]) {
			if (now) {
				if (!a[i]) {
					if (!r[i]) now=0;
				} else {
					if (f[i]) now=1;
					else now = r[i];
				}
			} else {
				if (a[i]) {
					if (r[i]) now=1;
				} else {
					if (f[i]) now=0;
					else now = r[i];
				}
			}
		}
		ans[i]=now;
	}
	return ans;
}

const int N=5555;
vector<int> adj[N];
int vis[N];
int ok[N];
int dfs(int u, int s) {
	if (vis[u] && u==s) return 1;
	if (vis[u]) return 0;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) z|=dfs(v,s);
	return z;
}
int dfs2(int u) {
	if (ok[u]) return 1;
	if (vis[u]) return 0;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) z|=dfs2(v);
	return z;
}
vector<int> p3(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> ans(n);
	forn(i,m) adj[u[i]].pb(v[i]);
	forn(i,n) if (r[i]) {
		forn(j,n) vis[j]=0;
		int q=dfs(i,i);
		ok[i]=q;
	}
	forn(i,n) {
		forn(j,n) vis[j]=0;
		int q=dfs2(i);
		ans[i]=q;
	}
	return ans;
}

int no[N];
int dfs(int u) {
	if (vis[u]) return 1;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) if (no[v]) continue; else z|=dfs(v);
}
vector<int> p4(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {
	int n=a.size(), m=u.size();
	vector<int> ans;
	forn(i,m) adj[u[i]].pb(v[i]);
	forn(i,n) no[i]=r[i];
	forn(i,n) {
		forn(i,n) vis[i]=0;
		ans[i]=dfs(i);
	}
	return ans;
}

vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v) {

	int n=a.size(), m=u.size();
	int z=1;
	forn(i,m) z&=(u[i]==v[i]) || (v[i]==(u[i]+1));
	if (z) {
		return p1(a,r,u,v);
	}
	z=1;
	forn(i,n) z&=a[i];
	if (z) return p3(a,r,u,v);
	forn(i,n) z|=a[i];
	if (!z) return p4(a,r,u,v);

}

Compilation message

train.cpp: In function 'int dfs(int)':
train.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 836 KB Output is correct
11 Correct 2 ms 724 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 1656 KB Output is correct
2 Correct 121 ms 1608 KB Output is correct
3 Correct 131 ms 1556 KB Output is correct
4 Correct 686 ms 1656 KB Output is correct
5 Correct 572 ms 1596 KB Output is correct
6 Correct 449 ms 1516 KB Output is correct
7 Correct 206 ms 1480 KB Output is correct
8 Correct 193 ms 1492 KB Output is correct
9 Correct 184 ms 1456 KB Output is correct
10 Correct 251 ms 1436 KB Output is correct
11 Correct 221 ms 1400 KB Output is correct
12 Correct 21 ms 1364 KB Output is correct
13 Correct 752 ms 1620 KB Output is correct
14 Correct 789 ms 1620 KB Output is correct
15 Correct 780 ms 1628 KB Output is correct
16 Correct 760 ms 1624 KB Output is correct
17 Correct 747 ms 1620 KB Output is correct
18 Correct 269 ms 1264 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 2112 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 2460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 3 ms 852 KB Output is correct
5 Correct 3 ms 856 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Correct 3 ms 736 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 836 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Runtime error 1 ms 596 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -