oj.uz

Submission #1064165

# Submission time Handle Problem Language Result Execution time Memory
1064165 2024-08-18T09:50:26 Z Ignut Toy Train (IOI17_train) C++17
22 / 100
 790 ms 1628 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5555;
int n, m;

vector<int> a, r;

vector<int> g[N];

bool ans = false;

int used[N];
bool good[N];

void dfs(int v) {
    used[v] = true;
    ans |= good[v];
    if (ans) return;
    for (int to : g[v])
        if (!used[to])
            dfs(to);
}

void dfs1(int v, int st) {
    if (good[st]) return;
    used[v] = true;
    for (int to : g[v]) {
        if (to == st) {
            good[st] = true; return;
        }
        if (!used[to]) dfs1(to, st);
    }
}

void dfs2(int v, int st) {
    if (good[st]) return;
    used[v] = true;
    for (int to : g[v]) {
        if (r[to] == 1) continue;
        if (to == st) {
            good[st] = true; return;
        }
        if (!used[to]) dfs2(to, st);
    }
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> u, vector<int> v) {
    n = A.size(), m = u.size();
    a = A, r = R;
    for (int i = 0; i < m; i ++) {
        g[u[i]].push_back(v[i]);
    }
    if (a[0] == 1) {
        // all Arez
        for (int i = 0; i < n; i ++) {
            if (r[i] == 0) continue;
            for (int j = 0; j < n; j ++) used[j] = false;
            dfs1(i, i);
        }
    }
    else {
        // all Borz
        for (int i = 0; i < n; i ++) {
            if (r[i] == 1) continue;
            for (int j = 0; j < n; j ++) used[j] = false;
            dfs2(i, i);
        }
    }

    vector<int> res;
    for (int s = 0; s < n; s ++) {
        ans = false;
        for (int i = 0; i < n; i ++) used[i] = 0;
        dfs(s);
        res.push_back(ans ^ (a[0] == 0));
    }
    return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1116 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 344 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 104 ms 1616 KB Output is correct
2 Correct 110 ms 1620 KB Output is correct
3 Correct 121 ms 1620 KB Output is correct
4 Correct 127 ms 1616 KB Output is correct
5 Correct 64 ms 1540 KB Output is correct
6 Correct 357 ms 1372 KB Output is correct
7 Correct 105 ms 1372 KB Output is correct
8 Correct 77 ms 1372 KB Output is correct
9 Correct 136 ms 1368 KB Output is correct
10 Correct 54 ms 1420 KB Output is correct
11 Correct 71 ms 1372 KB Output is correct
12 Correct 16 ms 1372 KB Output is correct
13 Correct 587 ms 1616 KB Output is correct
14 Correct 690 ms 1620 KB Output is correct
15 Correct 635 ms 1628 KB Output is correct
16 Correct 25 ms 1372 KB Output is correct
17 Correct 143 ms 1500 KB Output is correct
18 Correct 211 ms 1116 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 1360 KB Output is correct
2 Correct 90 ms 1364 KB Output is correct
3 Correct 88 ms 1428 KB Output is correct
4 Correct 16 ms 1372 KB Output is correct
5 Correct 243 ms 1372 KB Output is correct
6 Correct 261 ms 1368 KB Output is correct
7 Correct 259 ms 1368 KB Output is correct
8 Correct 61 ms 1392 KB Output is correct
9 Correct 12 ms 1372 KB Output is correct
10 Correct 790 ms 1548 KB Output is correct
11 Correct 683 ms 1532 KB Output is correct
12 Correct 749 ms 1548 KB Output is correct
13 Correct 274 ms 1372 KB Output is correct
14 Correct 171 ms 1388 KB Output is correct

Subtask #5
0 / 12.0

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