oj.uz

Submission #406860

# Submission time Handle Problem Language Result Execution time Memory
406860 2021-05-18T06:32:43 Z wiwiho Toy Train (IOI17_train) C++14
11 / 100
 1160 ms 1740 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> r;

vector<int> t;
vector<bool> vst;
void dfs1(int now){
    vst[now] = true;
    for(int i : rg[now]){
        if(!r[i] && !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(!r[i] && scc[i] == -1) dfs2(i, id);
    }
}

vector<bool> c;
bool ok = false;
void dfs(int now){
    vst[now] = true;
    //cerr << "owo " << now << "\n";
    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) {
    r = _r;
    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(r[i]) continue;
        if(!vst[i]) dfs1(i);
    }
    reverse(iter(t));
    int ts = 0;
    for(int i : t){
        if(r[i]) continue;
        if(scc[i] != -1) continue;
        dfs2(i, ts++);
    }

    //printv(scc, cerr);
    //printv(sz, cerr);
    
    for(int i = 0; i < n; i++){
        if(r[i]){
            c[i] = false;
            continue;
        }
        if(sz[scc[i]] > 1) c[i] = true;
    }
    //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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 1348 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 204 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 186 ms 1736 KB Output is correct
2 Correct 184 ms 1588 KB Output is correct
3 Correct 187 ms 1556 KB Output is correct
4 Incorrect 1115 ms 1528 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 897 ms 1300 KB Output is correct
2 Correct 157 ms 1512 KB Output is correct
3 Correct 325 ms 1628 KB Output is correct
4 Correct 477 ms 1628 KB Output is correct
5 Correct 374 ms 1732 KB Output is correct
6 Correct 327 ms 1640 KB Output is correct
7 Correct 365 ms 1732 KB Output is correct
8 Correct 328 ms 1580 KB Output is correct
9 Correct 36 ms 1356 KB Output is correct
10 Correct 1086 ms 1724 KB Output is correct
11 Correct 1055 ms 1708 KB Output is correct
12 Correct 1122 ms 1740 KB Output is correct
13 Correct 585 ms 1712 KB Output is correct
14 Correct 362 ms 1584 KB Output is correct

Subtask #5
0 / 12.0

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