oj.uz

Submission #775983

# Submission time Handle Problem Language Result Execution time Memory
775983 2023-07-07T08:03:29 Z ttamx Toy Train (IOI17_train) C++14
16 / 100
 9 ms 2004 KB 
#include "train.h"
#include<bits/stdc++.h>

using namespace std;

const int N=5005;
const int M=20005;

int n,m;
int a[N],r[N];
int vis[N];
vector<int> adj[N],radj[N];
vector<int> ans;
stack<int> st;
vector<vector<int>> scc;
int sccid[N];
int deg[N],del[N];
bool lose[N],win[N];
bool selfloop[N];
queue<int> q;

void scc1(int u,bool block=true){
	if(vis[u])return;
	vis[u]=true;
	for(auto v:adj[u])if(!block||!r[v])scc1(v,block);
	st.emplace(u);
}

void scc2(int u,bool block=true){
	if(vis[u])return;
	vis[u]=true;
	scc.back().emplace_back(u);
	sccid[u]=scc.size();
	for(auto v:radj[u])if(!block||!r[v])scc2(v,block);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	n=A.size();
	m=U.size();
    ans.resize(n);
	for(int i=0;i<n;i++)a[i]=A[i],r[i]=R[i];
    for(int i=0;i<m;i++){
        int u=U[i],v=V[i];
		if(u==v)selfloop[u]=true;
		else{
        	adj[u].emplace_back(v);
        	radj[v].emplace_back(u);
			deg[u]++;
		}
    }
	// cerr << "LOSE\n";
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=0;i<n;i++)if(!r[i])scc1(i);
	for(int i=0;i<n;i++)vis[i]=false;
	while(!st.empty()){
		auto u=st.top();
		st.pop();
		if(vis[u])continue;
		scc.emplace_back(vector<int>(0));
		scc2(u);
	}
	for(auto com:scc){
		bool ok=true;
		for(auto u:com){
			if(a[u]==0)continue;
			for(auto v:adj[u]){
				if(sccid[v]!=sccid[u]){
					ok=false;
					break;
				}
			}
			if(!ok)break;
		}
		if(com.size()==1&&!selfloop[com[0]])ok=false;
		// for(auto u:com)cerr << u << " ";
		// cerr << ": " << ok << "\n";
		if(ok)for(auto u:com)lose[u]=true;
	}
	// for(int i=0;i<n;i++)cerr << lose[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)if(lose[i])q.emplace(i);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto v:radj[u]){
			del[v]++;
			if(lose[v])continue;
			if(a[v]==0||(del[v]==deg[v]&&!(selfloop[v]&&r[v]))){
				lose[v]=true;
				q.emplace(v);
			}
		}
	}
	// for(int i=0;i<n;i++)cerr << lose[i] << " \n"[i==n-1];
	// cerr << "WIN\n";
	scc.clear();
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=0;i<n;i++)scc1(i,false);
	for(int i=0;i<n;i++)vis[i]=false;
	while(!st.empty()){
		auto u=st.top();
		st.pop();
		if(vis[u])continue;
		scc.emplace_back(vector<int>(0));
		scc2(u,false);
	}
	for(auto com:scc){
		bool ok=true,ok2=false;
		for(auto u:com){
			if(r[u]==1)ok2=true;
			if(a[u]==1)continue;
			for(auto v:adj[u]){
				if(sccid[v]!=sccid[u]){
					ok=false;
					break;
				}
			}
			if(!ok)break;
		}
		ok&=ok2;
		if(com.size()==1&&!selfloop[com[0]])ok=false;
		// for(auto u:com)cerr << u << " ";
		// cerr << ": " << ok << "\n";
		if(ok)for(auto u:com)if(!lose[u])win[u]=true;
	}
	// for(int i=0;i<n;i++)cerr << win[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)if(win[i])q.emplace(i);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto v:radj[u]){
			del[v]++;
			if(win[v])continue;
			if(a[v]==0||(del[v]==deg[v]&&!lose[v])){
				win[v]=true;
				q.emplace(v);
			}
		}
	}
	// for(int i=0;i<n;i++)cerr << win[i] << " \n"[i==n-1];
	for(int i=0;i<n;i++)ans[i]=win[i]&!lose[i];
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1804 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 4 ms 1532 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 4 ms 1492 KB Output is correct
8 Correct 4 ms 1492 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 5 ms 1364 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2004 KB Output is correct
2 Correct 6 ms 1876 KB Output is correct
3 Correct 6 ms 1900 KB Output is correct
4 Correct 9 ms 1744 KB Output is correct
5 Incorrect 7 ms 1620 KB 3rd lines differ - on the 39th token, expected: '1', found: '0'
6 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1504 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 7 ms 1764 KB Output is correct
4 Correct 8 ms 1620 KB Output is correct
5 Correct 7 ms 1876 KB Output is correct
6 Correct 7 ms 1748 KB Output is correct
7 Correct 7 ms 1756 KB Output is correct
8 Correct 7 ms 1620 KB Output is correct
9 Correct 6 ms 1608 KB Output is correct
10 Correct 7 ms 1764 KB Output is correct
11 Correct 7 ms 1748 KB Output is correct
12 Correct 7 ms 1748 KB Output is correct
13 Correct 8 ms 1748 KB Output is correct
14 Correct 7 ms 1620 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1804 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 4 ms 1532 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 4 ms 1492 KB Output is correct
7 Correct 4 ms 1492 KB Output is correct
8 Correct 4 ms 1492 KB Output is correct
9 Correct 4 ms 1492 KB Output is correct
10 Correct 5 ms 1364 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Incorrect 0 ms 468 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -