oj.uz

답안 #72902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72902 2018-08-27T08:04:28 Z mr_banana 장난감 기차 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -