Submission #1047959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047959		_8_8_	Toy Train (IOI17_train)	C++17	100 / 100	1295 ms	2136 KiB

train

#include <bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5e3 + 12;

vector<int> g[N],gt[N];
vector<int> a,r;
int n;
vector<int> make(vector<int> t) {
    vector<bool> vis(n,false),gd(n,false),l(n,false);
    for(int i:t) {
        l[i] = 1;
    }
    vector<int> col(n,0),bf;
    for(int i:t) {
        for(int to:g[i]) {
            if(l[to]) { 
                col[i]++;
            }
        }
    }
    bf = col;
    queue<int> q;
    for(int i:t) {
        if(r[i]) {
            vis[i] = 1;
            q.push(i);
        }
    }
    while(!q.empty()) {
        int v = q.front();q.pop();
        gd[v] = 1;
        for(int to:gt[v]) {
            if(vis[to] || !l[to]) continue;
            if(a[to] == 1) {
                q.push(to);
                vis[to] = 1;
            } else {
                col[to]--;
                if(!col[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
    vis.assign(n,false);
    col = bf;
    for(int i:t) {
        if(!gd[i]) {
            q.push(i);
            vis[i] = 1;
        }
    }
    while(!q.empty()) {
        int v = q.front();q.pop();
        gd[v] = 0;
        for(int to:gt[v]) {
            if(!l[to] || vis[to])continue;
            if(!a[to]) {
                q.push(to);
                vis[to] = 1;
            } else {
                col[to]--;
                if(!col[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
    vector<int> ret;
    for(int i:t) {
        if(gd[i]) ret.push_back(i);
    }
    return ret;
}
vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u, vector<int> v) {
    a = a_;
    r = r_;
    n = (int)a.size();
    for(int i = 0;i < (int)u.size();i++) {
        g[u[i]].push_back(v[i]);
        gt[v[i]].push_back(u[i]);
    }
    vector<int> f(n),res(n,0);
    iota(f.begin(),f.end(),0);
    // f = make(f);
    for(int i = 0;i < n;i++) {
        f = make(f);
    }
    for(int i:f) {
        res[i] = 1;
    }
    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