oj.uz

Submission #717172

# Submission time Handle Problem Language Result Execution time Memory
717172 2023-04-01T10:40:27 Z Jarif_Rahman Toy Train (IOI17_train) C++17
0 / 100
 992 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 215 ms 1620 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 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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