Submission #717171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
717171	2023-04-01T10:26:24 Z	Jarif_Rahman	Toy Train (IOI17_train)	C++17	11 / 100	15 ms	3412 KB

train

#include "train.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m, k;
vector<vector<int>> graph, graphr;
vector<bool> bl;
vector<int> order;
vector<int> cid;
vector<vector<int>> comp;
vector<bool> self_loop;

void dfs(int nd){
    if(bl[nd]) return;
    bl[nd] = 1;
    for(int x: graph[nd]) dfs(x);
    order.pb(nd);
}
void dfs2(int nd){
    if(cid[nd] != -1) return;
    cid[nd] = int(comp.size())-1;
    comp.back().pb(nd);
    for(int x: graphr[nd]) dfs2(x);
}

vector<vector<int>> scc;
vector<int> tsort;
void dfs3(int nd){
    if(bl[nd]) return;
    bl[nd] = 1;
    for(int x: scc[nd]) dfs3(x);
    tsort.pb(nd);
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V){
    n = A.size(), m = U.size();
    graph.resize(n), graphr.resize(n);
    bl.assign(n, 0);
    cid.assign(n, -1);
    self_loop.assign(n, 0);

    for(int i = 0; i < m; i++){
        if(U[i] == V[i]){
            self_loop[U[i]] = 1;
            continue;
        }
        graph[U[i]].pb(V[i]), graphr[V[i]].pb(U[i]);
    }
    for(int i = 0; i < n; i++) if(!bl[i]) dfs(i);
    reverse(order.begin(), order.end());
    for(int x: order) if(cid[x] == -1){
        comp.pb({});
        dfs2(x);
    }

    k = comp.size();
    scc.resize(k);

    set<pair<int,int>> scc_edges;
    for(int i = 0; i < n; i++) for(int x: graph[i]) if(cid[x] != cid[i])
        scc_edges.insert({cid[i], cid[x]});
    for(auto [a, b]: scc_edges) scc[a].pb(b);

    bl.assign(k, 0);
    for(int i = 0; i < k; i++) if(!bl[i]) dfs3(i);
    reverse(tsort.begin(), tsort.end());

    vector<bool> charger(k, 0);
    for(int _i = k-1, i = tsort[_i]; _i >= 0; _i--, i = tsort[_i]){
        if(comp[i].size() == 1){
            if(R[comp[i][0]] && self_loop[comp[i][0]]) charger[i] = 1;
        }
        else{
            for(int x: comp[i]) if(R[x]) charger[i] = 1;
        }
        for(int x: scc[i]) charger[i] = charger[i]|charger[x];
    }

    vector<int> ans;
    for(int i = 0; i < n; i++) ans.pb(charger[cid[i]]);
    return ans;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	2260 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	212 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	13 ms	3412 KB	Output is correct
2	Correct	12 ms	3136 KB	Output is correct
3	Correct	15 ms	3028 KB	Output is correct
4	Correct	8 ms	1852 KB	Output is correct
5	Correct	10 ms	2104 KB	Output is correct
6	Correct	10 ms	1980 KB	Output is correct
7	Correct	10 ms	1972 KB	Output is correct
8	Correct	8 ms	1620 KB	Output is correct
9	Correct	7 ms	1692 KB	Output is correct
10	Correct	9 ms	1724 KB	Output is correct
11	Correct	9 ms	1876 KB	Output is correct
12	Correct	11 ms	2516 KB	Output is correct
13	Correct	8 ms	1844 KB	Output is correct
14	Correct	9 ms	1720 KB	Output is correct
15	Correct	8 ms	1748 KB	Output is correct
16	Correct	8 ms	1844 KB	Output is correct
17	Correct	8 ms	1820 KB	Output is correct
18	Correct	10 ms	2388 KB	Output is correct