oj.uz

답안 #717173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
717173 2023-04-01T10:42:52 Z Jarif_Rahman 장난감 기차 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -