제출 #1070782

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

train

#include "bits/stdc++.h"
 
using namespace std;
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int> v){
    int n = a.size();
    int m = u.size();
    vector<int> adj[n+1],rev[n+1];
    for(int i = 0;i<u.size();i++){
        adj[u[i]].push_back(v[i]);
        rev[v[i]].push_back(u[i]);
    }
    vector<int> ans(n,1);
    int deg[n+1] = {0};
    int vis[n+1] = {0};
    int ch[n+1] = {0};
    while(1){
        for(int i = 0;i<n;i++){
            if(ans[i]){
                vis[i] = 0;ch[i] = 0;
                deg[i] = adj[i].size();
            }
        }
        queue<int> q;
        for(int i = 0;i<n;i++){
            if(ans[i]&&r[i]){
                q.push(i);
            }
        }
        while(!q.empty()){
            int x = q.front();q.pop();
            if(ch[x])continue;
            ch[x] = 1;
            for(auto i:rev[x]){
                deg[i]--;
                if(ans[i]&&(deg[i]==0||a[i]==1)&&!vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
        bool upd = 0;
        for(int i = 0;i<n;i++){
            int old = ans[i];
            ans[i]&=vis[i];
            if(old!=ans[i])upd = 1;
        }
        if(upd==0)break;
    }
    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:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i = 0;i<u.size();i++){
      |                   ~^~~~~~~~~
train.cpp:6:9: warning: unused variable 'm' [-Wunused-variable]
    6 |     int m = u.size();
      |         ^

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