Submission #471966

#	Time	Username	Problem	Language	Result	Execution time	Memory
471966		SHZhang	Toy Train (IOI17_train)	C++14	11 / 100	2092 ms	79924 KiB

train

#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, int> > que;
    for (int i = 0; i < n; i++) {
        if (r[i]) {
            f[i] = 1;
            que.push(make_pair(i, 0));
        }
    }
    while (!que.empty()) {
        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, f[pre]));
                    f[pre] = newf;
                }
            } else {
                freq[pre][pr.second]--;
                freq[pre][f[cur]]++;
                //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, old_f));
                }
            }
        }
    }
    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 (stderr)

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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51