제출 #555815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555815		Lemur95	장난감 기차 (IOI17_train)	C++17	11 / 100	300 ms	1748 KiB

train

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <chrono>
#include <cassert>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <random>
#include "train.h"

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#  define __builtin_popcountll __popcnt64
#endif

//#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define x first
#define y second
#define ld long double
#define ll long long
#define ull unsigned long long
#define us unsigned short
#define lsb(x) ((x) & (-(x)))
#define pii pair <int, int>
#define pll pair <ll, ll>

using namespace std;

ifstream in("test.in");
ofstream out("test.out");

mt19937 gen(time(0));
uniform_int_distribution <uint32_t> rng;

const int MOD = (int)1e9 + 7;

ll gcd(ll a, ll b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}

int n, m;

int s[200005], f[200005];
int st[200005];
ll dp[200005];

vector <int> who_wins(vector <int> a, vector <int> r, vector <int> u, vector <int> v) {
    n = a.size(), m = u.size();

    vector <int> g[5005], gr[5005];
    vector <int> in(n);

    for (int i = 0; i < m; i++) {
        g[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }

    while (true) {
        queue <int> q;
        vector <int> cnt(n);

        fill(cnt.begin(), cnt.end(), 0);
        vector <int> s = r;

        for (int i = 0; i < n; i++) {
            if (r[i])
                q.push(i);
        }

        while (!q.empty()) {
            int nod = q.front();
            q.pop();

            for (auto& fiu : gr[nod]) {
                cnt[fiu]++;

                if (!s[fiu]) {
                    if (a[fiu] && cnt[fiu]) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                    else if (!a[fiu] && cnt[fiu] == g[fiu].size()) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (!s[i])
                q.push(i);
            s[i] ^= 1;
        }

        while (!q.empty()) {
            int nod = q.front();
            q.pop();

            for (auto& fiu : gr[nod]) {
                cnt[fiu]++;

                if (!s[fiu]) {
                    if (!a[fiu] && cnt[fiu]) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                    else if (a[fiu] && cnt[fiu] == g[fiu].size()) {
                        s[fiu] = 1;
                        q.push(fiu);
                    }
                }
            }
        }

        bool flag = 1;
        for (int i = 0; i < n; i++) {
            if (r[i] && s[i])
                r[i] = 0, flag = 0;
        }

        if (flag) {
            vector <int> ans(n);

            for (int i = 0; i < n; i++)
                ans[i] = s[i] ^ 1;

            return ans;
        }
    }
}

/*void solve() {
    int n, m;
    cin >> n >> m;

    vector <int> a(n), r(n), u(m), v(m);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    for (int i = 0; i < m; i++) {
        cin >> u[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> v[i];
    }

    vector <int> ans = who_wins(a, r, u, v);

    for (auto& i : ans)
        cout << i << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    srand(time(0));

    int T = 1;

    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}*/

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

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:95:50: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                     else if (!a[fiu] && cnt[fiu] == g[fiu].size()) {
train.cpp:121:49: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                     else if (a[fiu] && cnt[fiu] == g[fiu].size()) {

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