제출 #471969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471969		SHZhang	장난감 기차 (IOI17_train)	C++14	26 / 100	2090 ms	89324 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, 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 = min(f[cur] + r[pre], n + 1);
                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] < n + 1) 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;
}

컴파일 시 표준 에러 (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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51