답안 #406822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406822 2021-05-18T05:43:29 Z wiwiho 장난감 기차 (IOI17_train) C++14
11 / 100
1156 ms 1696 KB
#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;
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Incorrect 867 ms 1476 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1156 ms 1508 KB 3rd lines differ - on the 2nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -