Submission #117706

#	Time	Username	Problem	Language	Result	Execution time	Memory
117706		Plurm	Toy Train (IOI17_train)	C++11	0 / 100	11 ms	1708 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];
int ememcnt[5005];
int bttcnt[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 loop[5005];
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    // Subtask 4
    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++);
    }
    for(int i = 0; i < m; i++){
        if(cc[u[i]] == cc[v[i]]){
            ememcnt[cc[u[i]]]++;
        }
    }
    vector<int> res;
    for(int i = 0; i < n; i++){
        if(r[i]){
            bttcnt[cc[i]]++;
            if(memcnt[i] == 1) gcc[cc[i]] = loop[i];
        }
    }
    for(int i = 0; i < cccnt; i++){
        gcc[i] |= memcnt[i] > 1 && ememcnt[i] - memcnt[i] < bttcnt[i];
    }
    for(int i = 0; i < n; i++){
        res.push_back(gcc[cc[i]] ? 1 : 0);
    }
	return res;
}

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