제출 #133392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133392		icypiggy	장난감 기차 (IOI17_train)	C++14	12 / 100	2068 ms	143608 KiB

train

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <string.h>

using namespace std;
const int n_max = 6000;
vector<int> backward[n_max]; // edges run in the reverse direction!
vector<int> adj[n_max];
int deg[n_max]; // this is the out degree
void init(vector<int> &u, vector<int> &v) {
    memset(deg, 0, sizeof(deg));
    for(int i=0; i<u.size(); i++) {
        backward[v[i]].push_back(u[i]);
        adj[u[i]].push_back(v[i]);
        deg[u[i]]++;
    }
}
vector<int> who_wins(vector<int> a,  vector<int> r, vector<int> u, vector<int> v) {
    init(u,v);
    vector<int> ans(a.size(), 0); // initially b always wins
    queue<int> bfs;
    for(int i=0; i<r.size(); i++) {
        if(r[i]) {
            bfs.push(i); // put in all the chargers
            ans[i] = 1;
        }
    }
    while(!bfs.empty()) {
        int next = bfs.front();
        bfs.pop();
        for(int i: backward[next]) {
            if(ans[i]==0) {
                if(a[i]) {
                    ans[i] = true;
                    bfs.push(i);
                } else {
                    deg[i]--;
                    if(deg[i]==0) {
                        ans[i] = true;
                        bfs.push(i);
                    }
                }
            }
        }
    }
    bool bad = false;
    for(int i=0; i<r.size(); i++) {
        if(r[i]) {
            if(a[i]) {
                r[i] = false;
                // you win as long as there exists an outgoing win
                for(int j: adj[i]) {
                    if(ans[j]) {
                        r[i] = true;
                    }
                }
            } else {
                for(int j: adj[i]) {
                    if(ans[j]==0) {
                        r[i] = false;
                    }
                }
            }
            if(r[i]==false) {
                //cout << "charger " << i << " is bad\n";
                bad = true;
            }
        }
    }
    return (bad ? who_wins(a,r,u,v) :ans);
}

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

train.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
train.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<u.size(); i++) {
                  ~^~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<r.size(); i++) {
                  ~^~~~~~~~~
train.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<r.size(); i++) {
                  ~^~~~~~~~~

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