Submission #406822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406822	2021-05-18T05:43:29 Z	wiwiho	Toy Train (IOI17_train)	C++14	11 / 100	1156 ms	1696 KB

train

#include "train.h"

#include<bits/stdc++.h>

#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define eb emplace_back

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

const ll MAX = 1LL << 60;

ostream& operator<<(ostream& o, pii p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int n, m;
vector<vector<int>> g, rg;

vector<int> t;
vector<bool> vst;
void dfs1(int now){
    vst[now] = true;
    for(int i : rg[now]){
        if(!vst[i]) dfs1(i);
    }
    t.eb(now);
}

vector<int> scc, sz;
void dfs2(int now, int id){
    scc[now] = id;
    sz[id]++;
    for(int i : g[now]){
        if(scc[i] == -1) dfs2(i, id);
    }
}

vector<bool> c;
bool ok = false;
void dfs(int now){
    vst[now] = true;
    if(c[now]) ok = true;
    for(int i : g[now]){
        if(!vst[i]) dfs(i);
    }
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    n = a.size(), m = u.size();
    c.resize(n);
    g.resize(n);
    rg.resize(n);

    for(int i = 0; i < m; i++){
        if(u[i] == v[i]){
            c[u[i]] = true;
            continue;
        }
        g[u[i]].eb(v[i]);
        rg[v[i]].eb(u[i]);
    }
    
    vst.resize(n);
    scc.resize(n, -1);
    sz.resize(n);

    for(int i = 0; i < n; i++){
        if(!vst[i]) dfs1(i);
    }
    reverse(iter(t));
    int ts = 0;
    for(int i : t){
        if(scc[i] != -1) continue;
        dfs2(i, ts++);
    }
    
    for(int i = 0; i < n; i++){
        if(sz[scc[i]] > 1) c[i] = true;
        if(!r[i]) c[i] = false;
    }
    //printv(c, cerr);

    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        ok = false;
        fill(iter(vst), false);
        //cerr << "test " << i << "\n";
        dfs(i);
        ans[i] = ok;
    }

    return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	234 ms	1260 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	1 ms	204 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	173 ms	1696 KB	Output is correct
2	Correct	185 ms	1684 KB	Output is correct
3	Correct	188 ms	1680 KB	Output is correct
4	Correct	1090 ms	1544 KB	Output is correct
5	Correct	877 ms	1492 KB	Output is correct
6	Correct	563 ms	1424 KB	Output is correct
7	Correct	512 ms	1404 KB	Output is correct
8	Correct	312 ms	1416 KB	Output is correct
9	Correct	285 ms	1420 KB	Output is correct
10	Correct	372 ms	1476 KB	Output is correct
11	Correct	331 ms	1364 KB	Output is correct
12	Correct	32 ms	1228 KB	Output is correct
13	Correct	1099 ms	1556 KB	Output is correct
14	Correct	1066 ms	1556 KB	Output is correct
15	Correct	1099 ms	1612 KB	Output is correct
16	Correct	1091 ms	1552 KB	Output is correct
17	Correct	1060 ms	1552 KB	Output is correct
18	Correct	294 ms	1276 KB	Output is correct