Submission #432650

#	Time	Username	Problem	Language	Result	Execution time	Memory
432650		Runtime_error_	Toy Train (IOI17_train)	C++14	11 / 100	1125 ms	1548 KiB

train

 #include "train.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int inf = 5e3+9;
int n,m;
vector<int> adj[inf];
bool vis[inf],charge[inf],NoStationCycle[inf];

bool incycle(int u,int goal){
    bool ret = 0;
    vis[u] = 1;
    if(charge[u])
        return 0;
    for(auto v:adj[u]){
        if(v == goal)
            return ret = 1;
        if(!vis[v])
            ret |= incycle(v,goal);
    }
    return ret;
}

bool findstation(int u){
    bool ret = 0;
    if(NoStationCycle[u])
        return ret = 1;
    vis[u] = 1;
    for(auto v:adj[u])
        if(!vis[v])
            ret |= findstation(v);
    return ret;
}

vector<int> who_wins(vector<int> a, vector<int> R, vector<int> U, vector<int> V) {
    vector<int> ret;
    n = a.size();m  = U.size();
    for(int i=0;i<m;i++)
        adj[U[i]].pb(V[i]);

    for(int i=0;i<n;i++)
        charge[i] = R[i];
    for(int i=0;i<n;i++){
        memset(vis,0,sizeof(vis));
        NoStationCycle[i] = incycle(i,i);
    }
    for(int i=0;i<n;i++){
        memset(vis,0,sizeof(vis));
        ret.pb(!findstation(i));
    }
    return ret;
}
/*
2 4
0 0
1 0
0 1
1 0
1 1
0 0
*/

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