oj.uz

Submission #471967

# Submission time Handle Problem Language Result Execution time Memory
471967 2021-09-12T02:27:46 Z SHZhang Toy Train (IOI17_train) C++14
26 / 100
 2000 ms 88228 KB 
#include <vector>
#include <queue>
#include "train.h"

using namespace std;

int n, m;
vector<int> rgraph[5005];
int f[5005];
int freq[5005][5005];

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v) {
	n = (int)a.size();
    m = (int)u.size();
    for (int i = 0; i < m; i++) {
        rgraph[v[i]].push_back(u[i]);
        freq[u[i]][0]++;
    }
    queue<pair<int, pair<int, int> > > que;
    for (int i = 0; i < n; i++) {
        if (r[i]) {
            f[i] = 1;
            que.push(make_pair(i, make_pair(0, 1)));
        }
    }
    while (!que.empty()) {
        pair<int, pair<int, int> > pr = que.front();
        //fprintf(stderr, "! %d %d\n", pr.first, pr.second);
        int cur = pr.first; que.pop();
        for (int idx = 0; idx < rgraph[cur].size(); idx++) {
            int pre = rgraph[cur][idx];
            if (f[pre] > n) continue;
            if (a[pre]) {
                int newf = f[cur] + r[pre];
                if (newf > f[pre]) {
                    que.push(make_pair(pre, make_pair(f[pre], newf)));
                    f[pre] = newf;
                }
            } else {
                freq[pre][pr.second.first]--;
                freq[pre][pr.second.second]++;
                //fprintf(stderr, "freq %d -%d +%d => %d %d\n", pre, pr.second, f[cur], freq[pre][pr.second], freq[pre][f[cur]]);
                int old_f = f[pre];
                while (freq[pre][f[pre] - r[pre]] == 0) f[pre]++;
                if (f[pre] > old_f) {
                    que.push(make_pair(pre, make_pair(old_f, f[pre])));
                }
            }
        }
    }
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        //fprintf(stderr, "%d ", f[i]);
        ans.push_back(f[i] > n ? 1 : 0);
    }
    return ans;
}

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:30:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int idx = 0; idx < rgraph[cur].size(); idx++) {
      |                           ~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 40644 KB Output is correct
2 Correct 578 ms 39928 KB Output is correct
3 Correct 688 ms 40372 KB Output is correct
4 Correct 553 ms 38660 KB Output is correct
5 Correct 566 ms 39432 KB Output is correct
6 Correct 625 ms 40468 KB Output is correct
7 Correct 175 ms 33628 KB Output is correct
8 Correct 653 ms 21156 KB Output is correct
9 Correct 631 ms 40916 KB Output is correct
10 Correct 586 ms 40484 KB Output is correct
11 Correct 591 ms 40776 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21244 KB Output is correct
2 Correct 179 ms 21232 KB Output is correct
3 Correct 206 ms 21324 KB Output is correct
4 Correct 558 ms 62612 KB Output is correct
5 Correct 721 ms 57148 KB Output is correct
6 Correct 43 ms 21196 KB Output is correct
7 Correct 73 ms 26344 KB Output is correct
8 Correct 512 ms 21176 KB Output is correct
9 Correct 18 ms 21196 KB Output is correct
10 Correct 762 ms 21296 KB Output is correct
11 Correct 659 ms 21316 KB Output is correct
12 Correct 21 ms 21068 KB Output is correct
13 Correct 1473 ms 21228 KB Output is correct
14 Correct 1501 ms 21268 KB Output is correct
15 Correct 1460 ms 21224 KB Output is correct
16 Correct 1469 ms 21220 KB Output is correct
17 Correct 1428 ms 21228 KB Output is correct
18 Correct 125 ms 21060 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1884 ms 79588 KB Output is correct
2 Correct 1941 ms 37644 KB Output is correct
3 Execution timed out 2098 ms 67188 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 40644 KB Output is correct
2 Correct 578 ms 39928 KB Output is correct
3 Correct 688 ms 40372 KB Output is correct
4 Correct 553 ms 38660 KB Output is correct
5 Correct 566 ms 39432 KB Output is correct
6 Correct 625 ms 40468 KB Output is correct
7 Correct 175 ms 33628 KB Output is correct
8 Correct 653 ms 21156 KB Output is correct
9 Correct 631 ms 40916 KB Output is correct
10 Correct 586 ms 40484 KB Output is correct
11 Correct 591 ms 40776 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 404 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 404 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 93 ms 21244 KB Output is correct
33 Correct 179 ms 21232 KB Output is correct
34 Correct 206 ms 21324 KB Output is correct
35 Correct 558 ms 62612 KB Output is correct
36 Correct 721 ms 57148 KB Output is correct
37 Correct 43 ms 21196 KB Output is correct
38 Correct 73 ms 26344 KB Output is correct
39 Correct 512 ms 21176 KB Output is correct
40 Correct 18 ms 21196 KB Output is correct
41 Correct 762 ms 21296 KB Output is correct
42 Correct 659 ms 21316 KB Output is correct
43 Correct 21 ms 21068 KB Output is correct
44 Correct 1473 ms 21228 KB Output is correct
45 Correct 1501 ms 21268 KB Output is correct
46 Correct 1460 ms 21224 KB Output is correct
47 Correct 1469 ms 21220 KB Output is correct
48 Correct 1428 ms 21228 KB Output is correct
49 Correct 125 ms 21060 KB Output is correct
50 Execution timed out 2097 ms 88228 KB Time limit exceeded
51 Halted 0 ms 0 KB -