oj.uz

Submission #1063542

# Submission time Handle Problem Language Result Execution time Memory
1063542 2024-08-17T20:09:34 Z Zicrus Toy Train (IOI17_train) C++17
15 / 100
 2000 ms 43000 KB 
#include <bits/stdc++.h>
#include "train.h"
using namespace std;

typedef long long ll;

ll n;
vector<int> a, r;
vector<vector<ll>> adj;

int solve(ll cur, vector<int> vst) {
    vst[cur] = 1;
    if (r[cur]) {
        for (auto &e : vst) {
            if (e == 1) e = 2;
        }
    }
    int player = a[cur];
    for (auto &e : adj[cur]) {
        if (player == 1 && vst[e] == 2) return 1;
        if (player == 0 && vst[e] == 1) return 0;
    }
    for (auto &e : adj[cur]) {
        if (vst[e]) continue;
        int val = solve(e, vst);
        if (player == val) return val;
    }
    return !player;
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> u, vector<int> v) {
    n = A.size();
    a = A; r = R;
	vector<int> res(n);
    adj = vector<vector<ll>>(n);
    for (int i = 0; i < u.size(); i++) {
        adj[u[i]].push_back(v[i]);
    }
    mt19937 mt(75834);
    for (auto &e : adj) shuffle(e.begin(), e.end(), mt);

    vector<int> vst(n);
    for (int i = 0; i < n; i++) {
        res[i] = solve(i, vst);
    }

	return res;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < u.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1640 KB Output is correct
2 Correct 186 ms 1808 KB Output is correct
3 Correct 151 ms 1700 KB Output is correct
4 Correct 158 ms 1784 KB Output is correct
5 Correct 140 ms 1768 KB Output is correct
6 Correct 108 ms 1616 KB Output is correct
7 Correct 108 ms 1528 KB Output is correct
8 Correct 103 ms 1564 KB Output is correct
9 Correct 51 ms 1404 KB Output is correct
10 Correct 23 ms 1164 KB Output is correct
11 Correct 12 ms 1032 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2027 ms 5004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 43000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 7772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1640 KB Output is correct
2 Correct 186 ms 1808 KB Output is correct
3 Correct 151 ms 1700 KB Output is correct
4 Correct 158 ms 1784 KB Output is correct
5 Correct 140 ms 1768 KB Output is correct
6 Correct 108 ms 1616 KB Output is correct
7 Correct 108 ms 1528 KB Output is correct
8 Correct 103 ms 1564 KB Output is correct
9 Correct 51 ms 1404 KB Output is correct
10 Correct 23 ms 1164 KB Output is correct
11 Correct 12 ms 1032 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Execution timed out 2027 ms 5004 KB Time limit exceeded
33 Halted 0 ms 0 KB -