oj.uz

Submission #72902

# Submission time Handle Problem Language Result Execution time Memory
72902 2018-08-27T08:04:28 Z mr_banana Toy Train (IOI17_train) C++17
11 / 100
 297 ms 26164 KB 
#include "train.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=5000+100;
bool g[MN][MN];
vector<int> adj[MN],radj[MN];
vector<int> topol;
bool mark[MN];
int cmp[MN],szcmp[MN];
int n,m;
void dfs(int v){
	mark[v]=1;
	for(int u:adj[v]){
		if(!mark[u]){
			dfs(u);
		}
	}
	topol.push_back(v);
}
void dfs2(int v,int cmpn){
	mark[v]=1;
	cmp[v]=cmpn;
	szcmp[cmpn]++;
	for(int u:radj[v]){
		if(!mark[u]){
			dfs2(u,cmpn);
		}
	}
}
void scc(){
	for(int i=0;i<n;i++){
		if(!mark[i]){
			dfs(i);
		}
	}
	memset(mark,0,sizeof mark);
	int cnt=0;
	for(int i=n-1;i>=0;i--){
		if(!mark[topol[i]]){
			dfs2(topol[i],cnt);
			cnt++;
		}
	}
}
void dfs3(int v){
	mark[v]=1;
	for(int i=0;i<n;i++){
		if(!mark[i] && g[i][v]){
			dfs3(i);
		}
	}
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v) {
	vector<int> res(a.size());
	n=a.size(),m=v.size();
	for(int i=0;i<m;i++){
		g[u[i]][v[i]]=1;
		if(r[u[i]]==0 && r[v[i]]==0){
			adj[u[i]].push_back(v[i]);
			radj[v[i]].push_back(u[i]);
		}
	}
	scc();
	memset(mark,0,sizeof mark);
	for(int i=0;i<n;i++){
		if(!mark[i] && r[i]==0 && (szcmp[cmp[i]]>1 || g[i][i])){
			dfs3(i);
		}
	}
	for(int i=0;i<n;i++){
		res[i]=1-mark[i];
	}
	return res;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 21084 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 129 ms 21160 KB Output is correct
2 Correct 177 ms 22156 KB Output is correct
3 Correct 198 ms 23220 KB Output is correct
4 Incorrect 118 ms 26164 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26164 KB Output is correct
2 Correct 107 ms 26164 KB Output is correct
3 Correct 267 ms 26164 KB Output is correct
4 Correct 216 ms 26164 KB Output is correct
5 Correct 149 ms 26164 KB Output is correct
6 Correct 159 ms 26164 KB Output is correct
7 Correct 162 ms 26164 KB Output is correct
8 Correct 297 ms 26164 KB Output is correct
9 Correct 100 ms 26164 KB Output is correct
10 Correct 26 ms 26164 KB Output is correct
11 Correct 25 ms 26164 KB Output is correct
12 Correct 25 ms 26164 KB Output is correct
13 Correct 168 ms 26164 KB Output is correct
14 Correct 120 ms 26164 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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