제출 #608816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608816		Mounir	Toy Train (IOI17_train)	C++14	100 / 100	1470 ms	48232 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second;
using namespace std;

const int N = 1e6;
bool aAlice[N];
vector<int> versMoi[N], voisins[N];
int fuckes[N];
int nNoeuds;
bool aAcces[N], propage[N];
bool estRecharge[N];

void updRecharges(){
    queue<int> file;
    for (int noeud = 0; noeud < nNoeuds; ++noeud){
        aAcces[noeud] = false;
        propage[noeud] = false;
        if (estRecharge[noeud])
            file.push(noeud);
        fuckes[noeud] = sz(voisins[noeud]);
    }
    
    while (!file.empty()){
        int noeud = file.front();
        file.pop();

        if (propage[noeud]) continue;
        propage[noeud] = true;

        for (int avant : versMoi[noeud]){
            fuckes[avant] --;
            if ((aAlice[avant] || fuckes[avant] == 0) && !aAcces[avant]){
                file.push(avant);
                aAcces[avant] = true;
            }
        }
    }

    for (int noeud = 0; noeud < nNoeuds; ++noeud)
        estRecharge[noeud] &= aAcces[noeud];
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {  
    nNoeuds = sz(a);
    for (int noeud = 0; noeud < nNoeuds; ++noeud){
        aAlice[noeud] = a[noeud];
        estRecharge[noeud] = r[noeud];
    }
    int nAretes = sz(u);
    for (int i = 0; i < nAretes; ++i){
        voisins[u[i]].pb(v[i]);
        versMoi[v[i]].pb(u[i]);
    }

    for (int i = 0; i < nNoeuds; ++i)
        updRecharges();
    vector<int> res(nNoeuds);
    for (int i = 0; i < nNoeuds; ++i){
        res[i] = aAcces[i];
    }
	return res;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51