Submission #1242217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242217		thelegendary08	Toy Train (IOI17_train)	C++17	16 / 100	811 ms	1792 KiB

train

#include "train.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
const int mxn = 5e3 + 5;
using namespace std;
vvi adj(mxn), revadj(mxn);
int n, m;
std::vector<signed> who_wins(std::vector<signed> a, std::vector<signed> r, std::vector<signed> u, std::vector<signed> v) {
	n = a.size(); m = u.size();
	vi nxt(n);
	vi cyc(n);
	f0r(i, m){
		if(u[i] + 1 == v[i])nxt[u[i]] = 1;
		else cyc[u[i]] = 1;
		adj[u[i]].pb(v[i]);
		revadj[v[i]].pb(u[i]);
	}
	bool s3 = 1;
	bool s2 = 1;
	f0r(i, n){
		if(a[i])s3 = 0;
		if(!a[i])s2 = 0;
	}
	vector<signed> ans(n);
	if(s3){
		vb good(n); //is there any loop without a charger containing me?
		f0r(i, n){
			if(r[i] == 0){
				queue<int>q;
				q.push(i);
				vb vis(n); vis[i] = 1;
				while(!q.empty()){
					int node = q.front();
					q.pop();
					for(auto u : adj[node]){
						if(r[u])continue;
						if(vis[u])continue;
						vis[u] = 1;
						q.push(u);
					}
				}
				for(auto u : revadj[i]){
					if(vis[u])good[i] = 1;
				}
			}
		}
		// for(auto u : good)cout<<u<<' '; cout<<endl;
		f0r(i,n)ans[i] = 1;
		f0r(i, n){
			queue<int>q;
			q.push(i);
			vb vis(n); vis[i] = 1;
			while(!q.empty()){
				int node = q.front();
				q.pop();
				for(auto u : adj[node]){
					if(vis[u])continue;
					vis[u] = 1;
					q.push(u);
				}
			}
			f0r(j, n){
				if(vis[j] && good[j])ans[i] = 0;
			}
			
		}
	}
	else{
		f0r(tt, n){
			int x = tt;
			if(cyc[x] && a[x] == 1 && r[x] == 1){
				ans[tt] = 1; continue;
			}
			if(cyc[x] && a[x] == 0 && r[x] == 0){
				ans[tt] = 0; continue;
			}
			bool ok = 0;
			while(nxt[x]){
				x++;
				if(cyc[x] && a[x] == 1 && r[x] == 1){
					ans[tt] = 1; ok = 1; break;
				}
				if(cyc[x] && a[x] == 0 && r[x] == 0){
					ans[tt] = 0; ok = 1; break;
				}
			}
			if(ok)continue;
			if(cyc[x] && r[x])ans[tt] = 1;
			else ans[tt] = 0;
		}
	}
	
	
	
	
	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51