oj.uz

Submission #607579

# Submission time Handle Problem Language Result Execution time Memory
607579 2022-07-26T20:26:18 Z yanndev Toy Train (IOI17_train) C++17
23 / 100
 812 ms 1108 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX = 5042;

int n;
int deg[MX];
bool seenCharge[MX];
bool vis[MX];
bool isOk[MX];
bool isAlice[MX];
bool isCharge[MX];
vector<int> rgraph[MX];

bool BFS() {
    queue<int> nxt {};
    for (int i = 0; i < n; i++)
        deg[i] = 0;
    for (int i = 0; i < n; i++) {
        for (auto& x: rgraph[i])
            deg[x]++;
        if (isCharge[i] && isOk[i])
            nxt.push(i);
        vis[i] = false;
    }

    //cout << layer << ' ' << (int)nxt.size() << '\n';
    
    while (!nxt.empty()) {
        auto cur = nxt.front();
        //cout << "cur is " << cur << '\n';
        nxt.pop();

        for (auto& x: rgraph[cur]) {
            if (!vis[x] && ((--deg[x] == 0) || isAlice[x])) {
                vis[x] = true;
                nxt.push(x);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (isOk[i] && !vis[i]) {
            isOk[i] = false;
            return true;
        }
    }

    return false;
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
    n = (int)a.size();

    for (int i = 0; i < (int)u.size(); i++)
        rgraph[v[i]].push_back(u[i]);
    
    for (int i = 0; i < n; i++) {
        isAlice[i] = a[i];
        isCharge[i] = r[i];
        isOk[i] = true;
    }

    while (BFS());

    vector<int> ans (n);
    for (int i = 0; i < n; i++)
        ans[i] = isOk[i];
    return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 1072 KB Output is correct
2 Correct 733 ms 1068 KB Output is correct
3 Correct 812 ms 1068 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 346 ms 1052 KB Output is correct
6 Correct 765 ms 1044 KB Output is correct
7 Correct 19 ms 1004 KB Output is correct
8 Correct 479 ms 1060 KB Output is correct
9 Correct 510 ms 1100 KB Output is correct
10 Correct 260 ms 1020 KB Output is correct
11 Correct 408 ms 1020 KB Output is correct
12 Correct 486 ms 980 KB Output is correct
13 Correct 6 ms 980 KB Output is correct
14 Correct 6 ms 1108 KB Output is correct
15 Correct 6 ms 1108 KB Output is correct
16 Correct 6 ms 996 KB Output is correct
17 Correct 6 ms 980 KB Output is correct
18 Correct 672 ms 856 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 980 KB Output is correct
2 Correct 6 ms 1108 KB Output is correct
3 Correct 337 ms 1052 KB Output is correct
4 Correct 6 ms 1020 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 326 ms 736 KB Output is correct
7 Correct 21 ms 884 KB Output is correct
8 Correct 44 ms 852 KB Output is correct
9 Correct 29 ms 900 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 13 ms 724 KB Output is correct

Subtask #6
0 / 51.0

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