Submission #117690

#	Time	Username	Problem	Language	Result	Execution time	Memory
117690		Plurm	Toy Train (IOI17_train)	C++14	11 / 100	647 ms	1912 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> g[5005];
vector<int> rg[5005];
bool found[5005];
stack<int> ord;
void dfs1(int u){
    if(found[u]) return;
    found[u] = true;
    for(int v : g[u]){
        dfs1(v);
    }
    ord.push(u);
}
int cc[5005];
int memcnt[5005];
bool gcc[5005];
void dfs2(int u, int c = 0){
    if(!found[u]) return;
    found[u] = false;
    cc[u] = c;
    memcnt[c]++;
    for(int v : rg[u]){
        dfs2(v, c);
    }
}
bool dfs3(int u){
    if(found[u]) return false;
    found[u] = true;
    for(int v : g[u]){
        if(dfs3(v)) return true;
    }
    return gcc[cc[u]];
}
bool loop[5005];
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    // Subtask 3
    int m = u.size();
    for(int i = 0; i < m; i++){
        g[u[i]].push_back(v[i]);
        rg[v[i]].push_back(u[i]);
        if(u[i] == v[i]) loop[u[i]] = true;
    }
    int n = a.size();
    for(int i = 0; i < n; i++){
        dfs1(i);
    }
    int cccnt = 0;
    while(!ord.empty()){
        int cur = ord.top();
        ord.pop();
        if(found[cur]) dfs2(cur, cccnt++);
    }
    vector<int> res;
    for(int i = 0; i < n; i++){
        if(r[i]){
            gcc[cc[i]] = memcnt[cc[i]] > 1 || loop[i];
        }
    }
    for(int i = 0; i < n; i++){
        memset(found, false, sizeof(found));
        res.push_back(dfs3(i));
    }
	return res;
}

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