oj.uz

Submission #717173

# Submission time Handle Problem Language Result Execution time Memory
717173 2023-04-01T10:42:52 Z Jarif_Rahman Toy Train (IOI17_train) C++17
11 / 100
 1016 ms 2228 KB 
#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, G, GR;
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: G[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: GR[nd]) dfs2(x);
}
void dfs3(int nd){
    if(bl[nd]) return;
    bl[nd] = 1;
    for(int x: graph[nd]) dfs3(x);
}

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), G.resize(n), GR.resize(n);
    bl.assign(n, 0);
    cid.assign(n, -1);
    self_loop.assign(n, 0);

    for(int i = 0; i < m; i++){
        graph[U[i]].pb(V[i]);
        if(R[U[i]] || R[V[i]]) continue;
        if(U[i] == V[i]){
            self_loop[U[i]] = 1;
            continue;
        }
        G[U[i]].pb(V[i]), GR[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();
    vector<bool> non_charger(n, 0);
    for(int i = 0; i < k; i++){
        if(comp[i].size() > 1 || (comp[i].size() == 1 && self_loop[comp[i][0]])){
            for(int x: comp[i]) non_charger[x] = 1;
        }
    }

    vector<int> ans;
    for(int i = 0; i < n; i++){
        bl.assign(n, 0);
        dfs3(i);
        bool ok = 0;
        for(int j = 0; j < n; j++) if(bl[j] && non_charger[j]) ok = 1;
        ans.pb(!ok);
    }
    return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 1620 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
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 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 2228 KB Output is correct
2 Correct 230 ms 2052 KB Output is correct
3 Correct 228 ms 1968 KB Output is correct
4 Incorrect 957 ms 1740 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 1568 KB Output is correct
2 Correct 202 ms 2072 KB Output is correct
3 Correct 367 ms 2148 KB Output is correct
4 Correct 499 ms 1976 KB Output is correct
5 Correct 442 ms 2132 KB Output is correct
6 Correct 386 ms 2216 KB Output is correct
7 Correct 443 ms 2168 KB Output is correct
8 Correct 361 ms 2064 KB Output is correct
9 Correct 47 ms 1748 KB Output is correct
10 Correct 936 ms 1960 KB Output is correct
11 Correct 921 ms 1944 KB Output is correct
12 Correct 956 ms 1968 KB Output is correct
13 Correct 522 ms 2216 KB Output is correct
14 Correct 311 ms 2036 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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