oj.uz

답안 #291118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291118 2020-09-04T17:21:24 Z shayan_p 장난감 기차 (IOI17_train) C++17
16 / 100
 375 ms 2688 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 : 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]){
	if(!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){
		    assert(pwr[i]);
		    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];
    }
    for(int i = 0; i < sz(e1); i++){
	v[e1[i]].PB(e2[i]);
	rv[e2[i]].PB(e1[i]);
    }
    int DID = 0;
    while(DID <= 5){
	DID+= !iter();
    }
    vector<int> ans;
    for(int i = 0; i < n; i++){
	ans.PB(!del[i]);
    }
    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 1532 KB Output is correct
2 Correct 241 ms 1528 KB Output is correct
3 Correct 338 ms 1528 KB Output is correct
4 Correct 14 ms 1408 KB Output is correct
5 Correct 19 ms 1408 KB Output is correct
6 Correct 15 ms 1408 KB Output is correct
7 Correct 14 ms 1408 KB Output is correct
8 Correct 11 ms 1408 KB Output is correct
9 Correct 9 ms 1408 KB Output is correct
10 Correct 11 ms 1408 KB Output is correct
11 Correct 11 ms 1408 KB Output is correct
12 Correct 9 ms 1408 KB Output is correct
13 Correct 15 ms 1408 KB Output is correct
14 Correct 15 ms 1408 KB Output is correct
15 Correct 15 ms 1408 KB Output is correct
16 Correct 17 ms 1408 KB Output is correct
17 Correct 15 ms 1408 KB Output is correct
18 Correct 375 ms 1192 KB Output is correct

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 11 ms 2688 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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