oj.uz

답안 #358548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
358548 2021-01-25T19:00:47 Z Kerim 장난감 기차 (IOI17_train) C++17
16 / 100
 216 ms 11756 KB 
#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;
}
bool dfs2(int nd,int root){
	if(col[nd])return 0;
	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,int sen){
	if(ans[nd]==sen)return;
	ans[nd]=sen;
	tr(it,inv[nd])
		dfs1(*it,sen);	
}
int same[MAXN],go[MAXN],who[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],who[i]=a[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[i]=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,1);
			}
	}
	else if(subtask4){
		for(int i=0;i<n;i++)ans[i]=1;
		for(int i=0;i<n;i++)
			if(!col[i]){
				for(int j=0;j<n;j++)vis[j]=0;
				int ret=dfs2(i,i);
				if(ret)
					dfs1(i,0);
			}
	}
	else assert(0);
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5612 KB Output is correct
2 Correct 8 ms 5612 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 8 ms 5612 KB Output is correct
8 Correct 8 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 8 ms 5612 KB Output is correct
11 Correct 7 ms 5612 KB Output is correct

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 16 ms 5996 KB Output is correct
2 Correct 32 ms 5996 KB Output is correct
3 Correct 57 ms 6124 KB Output is correct
4 Correct 139 ms 6144 KB Output is correct
5 Correct 35 ms 5996 KB Output is correct
6 Correct 89 ms 5996 KB Output is correct
7 Correct 216 ms 5996 KB Output is correct
8 Correct 14 ms 6016 KB Output is correct
9 Correct 11 ms 5868 KB Output is correct
10 Correct 14 ms 5868 KB Output is correct
11 Correct 12 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 178 ms 5740 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 5868 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 5612 KB Output is correct
2 Correct 8 ms 5612 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5624 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 8 ms 5612 KB Output is correct
7 Correct 8 ms 5612 KB Output is correct
8 Correct 8 ms 5612 KB Output is correct
9 Correct 8 ms 5612 KB Output is correct
10 Correct 8 ms 5612 KB Output is correct
11 Correct 7 ms 5612 KB Output is correct
12 Runtime error 10 ms 9964 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -