Submission #117690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117690	2019-06-17T06:33:30 Z	Plurm	Toy Train (IOI17_train)	C++14	11 / 100	647 ms	1912 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	279 ms	1380 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	512 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	237 ms	1788 KB	Output is correct
2	Correct	266 ms	1792 KB	Output is correct
3	Correct	228 ms	1912 KB	Output is correct
4	Correct	58 ms	1792 KB	Output is correct
5	Correct	279 ms	1784 KB	Output is correct
6	Correct	647 ms	1784 KB	Output is correct
7	Correct	13 ms	1664 KB	Output is correct
8	Correct	163 ms	1784 KB	Output is correct
9	Correct	368 ms	1784 KB	Output is correct
10	Correct	134 ms	1644 KB	Output is correct
11	Correct	186 ms	1600 KB	Output is correct
12	Correct	28 ms	1576 KB	Output is correct
13	Correct	42 ms	1792 KB	Output is correct
14	Correct	68 ms	1792 KB	Output is correct
15	Correct	39 ms	1792 KB	Output is correct
16	Correct	51 ms	1792 KB	Output is correct
17	Correct	38 ms	1792 KB	Output is correct
18	Correct	427 ms	1612 KB	Output is correct