답안 #358546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
358546	2021-01-25T18:52:34 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{
					if(col[j] and same[j])
						ans[j]=1;
					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	5612 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	18 ms	6124 KB	Output is correct
2	Correct	33 ms	6124 KB	Output is correct
3	Correct	57 ms	5996 KB	Output is correct
4	Correct	141 ms	5996 KB	Output is correct
5	Correct	33 ms	6028 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	5868 KB	Output is correct
9	Correct	14 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	13 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	12 ms	5996 KB	Output is correct
18	Correct	180 ms	5740 KB	Output is correct