답안 #358545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
358545	2021-01-25T18:48:09 Z	Kerim	장난감 기차 (IOI17_train)	C++17	11 / 100	219 ms	11756 KB

train

#include "train.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int col[MAXN],vis[MAXN],res,n,m;
vector<int>adj[MAXN],inv[MAXN],ans;
bool dfs(int nd,int root){
	if(vis[nd])return (nd==root);
	vis[nd]=1;
	tr(it,adj[nd])
		if(dfs(*it,root))return 1;
	return 0;
}
void dfs1(int nd){
	if(ans[nd])return;
	ans[nd]=1;
	tr(it,inv[nd])
		dfs1(*it);	
}
int same[MAXN],go[MAXN];
vector<int> who_wins(vector<int> a, vector<int> r,vector<int> u,vector<int> v) {
	n=int(a.size());m=int(u.size());
	for(int i=0;i<n;i++)col[i]=r[i];
	int subtask3=1,subtask4=1,subtask1=1;
	for(int i=0;i<n;i++)subtask3&=(a[i]),subtask4&=(!a[i]);
	ans.resize(n);for(int i=0;i<n;i++)ans[i]=0;
	for(int i=0;i<m;i++)
		adj[u[i]].pb(v[i]),inv[v[i]].pb(u[i]),subtask1&=(v[i]==u[i] or v[i]==u[i]+1);
	if(subtask1){
		for(int i=0;i<n;i++)
			tr(it,adj[i])
				same[i]|=(*it==i),go[i]|=(*it==i+1);
		for(int i=0;i<n;i++){
			int j=i;
			while(1){
				if(same[j] and col[j]==a[j]){
					ans[i]=a[j];
					break;
				}
				if(go[j])
					j++;
				else
					break;
			}
		}
	}
	else if(subtask3){
		for(int i=0;i<n;i++)
			if(col[i]){
				for(int j=0;j<n;j++)vis[j]=0;
				int ret=dfs(i,i);
				if(ret)
					dfs1(i);
			}
	}
	else if(subtask4){
			
	}
	else assert(0);
	return ans;
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5612 KB	Output is correct
2	Incorrect	8 ms	5740 KB	3rd lines differ - on the 4997th token, expected: '1', found: '0'
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	10 ms	9964 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	5996 KB	Output is correct
2	Correct	32 ms	6124 KB	Output is correct
3	Correct	59 ms	5996 KB	Output is correct
4	Correct	145 ms	6124 KB	Output is correct
5	Correct	34 ms	6124 KB	Output is correct
6	Correct	87 ms	5996 KB	Output is correct
7	Correct	219 ms	5868 KB	Output is correct
8	Correct	12 ms	5884 KB	Output is correct
9	Correct	11 ms	5868 KB	Output is correct
10	Correct	14 ms	5868 KB	Output is correct
11	Correct	11 ms	5868 KB	Output is correct
12	Correct	11 ms	5868 KB	Output is correct
13	Correct	12 ms	5996 KB	Output is correct
14	Correct	12 ms	5996 KB	Output is correct
15	Correct	12 ms	5996 KB	Output is correct
16	Correct	12 ms	5996 KB	Output is correct
17	Correct	14 ms	5996 KB	Output is correct
18	Correct	177 ms	5868 KB	Output is correct