oj.uz

답안 #291132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291132 2020-09-04T17:46:38 Z shayan_p 장난감 기차 (IOI17_train) C++17
0 / 100
 9 ms 2304 KB 
#include<bits/stdc++.h>
#include "train.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 5010, inf = 1e9 + 10, mod = 1e9 + 7;

bool who[maxn], del[maxn], pwr[maxn];
vector<int> v[maxn], rv[maxn];
int n;

int d[maxn];

bool iter(){    
    for(int i = 0; i < n; i++){
	d[i] = sz(v[i]);
    }
    queue<int> q;
    for(int i = 0; i < n; i++){
	if(pwr[i] && !del[i]){
	    q.push(i);
	}
    }
    while(sz(q)){
	int u = q.front();
	q.pop();
	d[u] = -1;
	
	for(int y : v[u]){
	    assert(d[y] < 0);
	}
	
	for(int y : rv[u]){
	    if(!del[y] && who[y] && d[y] >= 0)
		q.push(y);
	    if(!del[y] && !who[y] && --d[y] == 0)
		q.push(y);
	}
    }
    bool yes = 0;	
    for(int i = 0; i < n; i++){
	if(!del[i] && d[i] >= 0)
	    del[i] = 1, yes = 1;
    }
    for(int i = 0; i < n; i++){
	if(pwr[i] && !del[i]){
	    bool any = 0, all = 1;
	    for(int x : v[i])
		any|= del[x], all&= del[x];
	    if(who[i]){
		if(all){
		    del[i] = 1;
		    yes = 1;
		}
	    }
	    else{
		if(any){
		    del[i] = 1;
		    yes = 1;
		}
	    }
	}
    }
    return yes;
}

vector<int> who_wins(vector<int> _a, vector<int> _r, vector<int> e1, vector<int> e2){
    ::n = sz(_a);
    for(int i = 0; i < n; i++){
	who[i] = _a[i];
	pwr[i] = _r[i];

	assert(who[i] == 0); /////////
    }
    assert(sz(e1) == sz(e2));
    for(int i = 0; i < sz(e1); i++){
	v[e1[i]].PB(e2[i]);
	rv[e2[i]].PB(e1[i]);
    }
    while(iter()){
    }
    vector<int> ans;
    for(int i = 0; i < n; i++){
	ans.PB(!del[i]);
    }
    return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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