oj.uz

Submission #53198

# Submission time Handle Problem Language Result Execution time Memory
53198 2018-06-29T01:23:54 Z WA_TLE Toy Train (IOI17_train) C++14
11 / 100
 18 ms 5604 KB 
#include "train.h"
#include<vector>
#include<queue>
using namespace std;
#define pub push_back
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	int i,j,n=a.size(),m=u.size();
	vector<vector<int>>go(n);
	vector<vector<int>>rev(n);
	//サイクルになりうるのを求める
	for(i=0;i<m;i++){
		go[u[i]].pub(v[i]);
		rev[v[i]].pub(u[i]);
	}
	vector<int>cir(n);
	queue<int>que;
	for(i=0;i<n;i++){
		if(r[i]){que.push(i);}
		else if(a[i]){cir[i]=1;}
		else{cir[i]=go[i].size();}
	}
	//cirが0以下ならチャー駅に行ける(勝つとは言ってない)
	//0より大きいなら即Bの勝ち
	while(que.size()>0){
		int ter=que.front();
		que.pop();
		for(auto it:rev[ter]){
			if(cir[it]==1){que.push(it);}
			cir[it]--;
		}
	}
	vector<int>bwi(n);
	for(i=0;i<n;i++){
		if(cir[i]>0){que.push(i);}
		else if(a[i]){bwi[i]=go[i].size();}
		else{bwi[i]=1;}
	}
	while(que.size()>0){
		int ter=que.front();
		que.pop();
		for(auto it:rev[ter]){
			if(bwi[it]==1){que.push(it);}
			bwi[it]--;
		}
	}
	vector<int>ans(n);
	for(i=0;i<n;i++){if(bwi[i]>0){ans[i]=1;}}
	return ans;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:7:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,n=a.size(),m=u.size();
        ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1144 KB Output is correct
2 Correct 2 ms 1144 KB Output is correct
3 Correct 2 ms 1144 KB Output is correct
4 Incorrect 2 ms 1144 KB 3rd lines differ - on the 4th token, expected: '0', found: '1'
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2044 KB Output is correct
2 Correct 10 ms 2324 KB Output is correct
3 Correct 11 ms 2632 KB Output is correct
4 Correct 11 ms 2968 KB Output is correct
5 Correct 11 ms 3108 KB Output is correct
6 Correct 11 ms 3184 KB Output is correct
7 Correct 12 ms 3384 KB Output is correct
8 Correct 11 ms 3584 KB Output is correct
9 Correct 10 ms 3780 KB Output is correct
10 Correct 12 ms 4096 KB Output is correct
11 Correct 11 ms 4300 KB Output is correct
12 Correct 18 ms 4512 KB Output is correct
13 Correct 12 ms 4736 KB Output is correct
14 Correct 11 ms 4832 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5136 KB Output is correct
2 Correct 11 ms 5356 KB Output is correct
3 Correct 12 ms 5544 KB Output is correct
4 Correct 12 ms 5604 KB Output is correct
5 Correct 2 ms 5604 KB Output is correct
6 Correct 6 ms 5604 KB Output is correct
7 Correct 7 ms 5604 KB Output is correct
8 Incorrect 7 ms 5604 KB 3rd lines differ - on the 5th token, expected: '0', found: '1'
9 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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