답안 #56264 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56264	2018-07-10T18:32:46 Z	ngkan146	장난감 기차 (IOI17_train)	C++11	11 / 100	613 ms	93896 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
#define AREZOU 1
#define BORZOU 0

int n, m;
vector <int> G[5005];
vector <int> Gback[5005];
int owner[5005];
int chargingStation[5005];
int result[5005];
int deg[5005];

bool curVer[5005], visited[5005], ok[5005], del[5005];
void solve(vector <int> lst){
    //for(auto v: lst)    cout << v << ' '; cout << endl;
    memset(curVer, 0, sizeof(curVer));
    memset(visited, 0, sizeof(visited));
    memset(ok, 0, sizeof(ok));

    for(auto u: lst){
        ok[u] = 1;
        curVer[u] = 1;
        for(auto v: Gback[u]){
            if (curVer[v])  deg[v] ++;
        }
    }

    vector <int> goodForArezou;
    vector <int> goodForBorzou;
    queue <int> q;

    for(auto v: lst)
        if (chargingStation[v]) q.push(v), visited[v] = 1;

    while(q.size()){
        int u = q.front();
        q.pop();
        goodForArezou.push_back(u);
        for(auto v: Gback[u]){
            if (!curVer[v]) continue;
            -- deg[v];
            if (!visited[v] && (owner[v] == AREZOU || !deg[v])){
                visited[v] = 1;
                q.push(v);
            }
        }
    }

    for(auto v: goodForArezou)  ok[v] = 0;
    memset(visited, 0, sizeof(visited));
    for(int i=0;i<n;i++){
        deg[i] = 0;
        if (ok[i])  q.push(i), visited[i] = 1;
    }
    for(auto u: lst){
        for(auto v: Gback[u]){
            if (curVer[v])  deg[v] ++;
        }
    }
    while(q.size()){
        int u = q.front();
        q.pop();
        goodForBorzou.push_back(u);
        for(auto v: Gback[u]){
            if (!curVer[v]) continue;
            -- deg[v];
            if (!visited[v] && (owner[v] == BORZOU || !deg[v])){
                visited[v] = 1;
                q.push(v);
            }
        }
    }

    for(auto v: goodForBorzou)  del[v] = 1;
    vector <int> newLst;
    for(int i=0;i<n;i++)    if (!del[i])    newLst.push_back(i);
    if (lst == newLst) {for(auto v: lst) result[v] = 1; return;}
    solve(newLst);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V) {
	n = A.size();
	for(int i=0;i<n;i++)
        owner[i] = A[i],
        chargingStation[i] = R[i];
    m = U.size();
    for(int i=0;i<m;i++){
        Gback[V[i]].push_back(U[i]);
    }
    vector <int> lst;
    for(int i=0;i<n;i++)    lst.push_back(i);
    solve(lst);
    vector <int> res;
    for(int i=0;i<n;i++)    res.push_back(result[i]);
    return res;
}
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	190 ms	29768 KB	Output is correct
2	Correct	388 ms	50492 KB	Output is correct
3	Correct	473 ms	60636 KB	Output is correct
4	Correct	11 ms	60636 KB	Output is correct
5	Correct	12 ms	60636 KB	Output is correct
6	Correct	12 ms	60636 KB	Output is correct
7	Correct	11 ms	60636 KB	Output is correct
8	Correct	11 ms	60636 KB	Output is correct
9	Correct	10 ms	60636 KB	Output is correct
10	Correct	10 ms	60636 KB	Output is correct
11	Correct	10 ms	60636 KB	Output is correct
12	Correct	10 ms	60636 KB	Output is correct
13	Correct	10 ms	60636 KB	Output is correct
14	Correct	10 ms	60636 KB	Output is correct
15	Correct	11 ms	60636 KB	Output is correct
16	Correct	11 ms	60636 KB	Output is correct
17	Correct	11 ms	60636 KB	Output is correct
18	Correct	613 ms	93896 KB	Output is correct