oj.uz

Submission #778542

# Submission time Handle Problem Language Result Execution time Memory
778542 2023-07-10T12:00:26 Z I_Love_EliskaM_ Toy Train (IOI17_train) C++14
16 / 100
 787 ms 1512 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 dfs3(int u) {
	if (vis[u]) return 1;
	vis[u]=1;
	int z=0;
	for(auto&v:adj[u]) if (!no[v]) z|=dfs3(v);
	return z;
}
void dfs4(int u) {
	if (vis[u]) return;
	vis[u]=1;
	for(auto&v:adj[u]) {
		dfs4(v);
		ok[u]|=ok[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(n);
	forn(i,m) adj[u[i]].pb(v[i]);
	forn(i,n) no[i]=r[i];
	forn(i,n) {
		forn(j,n) vis[j]=0;
		ok[i]=dfs3(i);
	}
	forn(i,n) {
		forn(j,n) vis[j]=0;
		dfs4(i);
	}
	forn(i,n) ans[i]=!ok[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);
	exit(1);

}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 1512 KB Output is correct
2 Correct 124 ms 1476 KB Output is correct
3 Correct 141 ms 1456 KB Output is correct
4 Correct 676 ms 1420 KB Output is correct
5 Correct 593 ms 1376 KB Output is correct
6 Correct 449 ms 1312 KB Output is correct
7 Correct 217 ms 1268 KB Output is correct
8 Correct 197 ms 1280 KB Output is correct
9 Correct 163 ms 1260 KB Output is correct
10 Correct 253 ms 1252 KB Output is correct
11 Correct 216 ms 1204 KB Output is correct
12 Correct 19 ms 1192 KB Output is correct
13 Correct 774 ms 1404 KB Output is correct
14 Correct 755 ms 1416 KB Output is correct
15 Correct 787 ms 1416 KB Output is correct
16 Correct 768 ms 1416 KB Output is correct
17 Correct 779 ms 1484 KB Output is correct
18 Correct 266 ms 1148 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 1236 KB Output is correct
2 Incorrect 187 ms 1388 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 724 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
13 Halted 0 ms 0 KB -