제출 #1047404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047404		becaido	장난감 기차 (IOI17_train)	C++17	100 / 100	150 ms	1880 KiB

train

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#include "grader.cpp"
#else
#include "train.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5005;

int n, m;
int ans[SIZE], d[SIZE];
bool alice[SIZE], is[SIZE];
vector<int> adj[SIZE], rev[SIZE];

bool vs[SIZE];
int deg[SIZE];
vector<int> cal(vector<int> v, bool x) {
    fill(vs + 1, vs + n + 1, 0);
    fill(deg + 1, deg + n + 1, 0);
    queue<int> q;
    for (int pos : v) {
        q.push(pos);
        vs[pos] = 1;
    }
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int lp : rev[pos]) if (vs[lp] == 0 && ans[lp] == 0 && (alice[lp] == x || ++deg[lp] == d[lp])) {
            q.push(lp);
            vs[lp] = 1;
        }
    }
    v.clear();
    FOR (i, 1, n) if (vs[i]) v.pb(i);
    return v;
}

vector<int> who_wins(vector<int> a_, vector<int> r_, vector<int> u, vector<int> v) {
    n = a_.size();
    m = u.size();
    FOR (i, 1, n) {
        alice[i] = a_[i - 1];
        is[i] = r_[i - 1];
        adj[i].clear();
        rev[i].clear();
        ans[i] = d[i] = 0;
    }
    FOR (i, 0, m - 1) {
        u[i]++, v[i]++;
        d[u[i]]++;
        adj[u[i]].pb(v[i]);
        rev[v[i]].pb(u[i]);
    }
    while (true) {
        int cnt = 0;
        FOR (i, 1, n) if (ans[i] == 0) cnt++;
        if (cnt == 0) break;
        vector<int> A, B;
        FOR (i, 1, n) if (is[i] && ans[i] == 0) A.pb(i);
        A = cal(A, 1);
        if (A.size() == cnt) {
            for (int x : A) ans[x] = 1;
            break;
        }
        for (int i = 1, j = 0; i <= n; i++) if (ans[i] == 0) {
            while (j < A.size() && A[j] < i) j++;
            if (j < A.size() && A[j] == i) continue;
            B.pb(i);
        }
        B = cal(B, 0);
        for (int x : B) {
            ans[x] = 2;
            for (int lp : rev[x]) d[lp]--;
        }
    }
    vector<int> res;
    FOR (i, 1, n) res.pb(ans[i] == 1 ? 1 : 0);
    return res;
}

/*
in1
2 4
0 1
1 0
0 0
0 1
1 0
1 1
out1
1 1
*/

컴파일 시 표준 에러 (stderr) 메시지

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:81:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |         if (A.size() == cnt) {
      |             ~~~~~~~~~^~~~~~
train.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (j < A.size() && A[j] < i) j++;
      |                    ~~^~~~~~~~~~
train.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             if (j < A.size() && A[j] == i) continue;
      |                 ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51