제출 #591551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591551		knon0501	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	327 ms	31740 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=4e5+5;

long long deg[MX];
int vis[MX];
vector<int> a[MX];
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    vector<int> v;
    for(int i=0 ; i<n ; i++){
        v.push_back(s[i]);
        v.push_back(t[i]);
    }
    sort(v.begin(),v.end());

    v.erase(unique(v.begin(),v.end()),v.end());

    for(int i=0 ; i<n ; i++){
        deg[lower_bound(v.begin(),v.end(),s[i])-v.begin()]++;
        deg[lower_bound(v.begin(),v.end(),t[i])-v.begin()]--;
        a[lower_bound(v.begin(), v.end(), s[i]) - v.begin()].push_back(lower_bound(v.begin(), v.end(), t[i]) - v.begin());
    }
    if(v.size()==1)return 0;
    if(deg[0]>1)return 1;
    if(deg[0]<=0)a[0].push_back(1);
    deg[1]+=deg[0]-1;
    for(int i=1 ; i<(int)v.size()-1 ; i++){
        if(deg[i]<0){
            a[i].push_back(i+1);
        }
        if(deg[i]>0)return 1;
        deg[i+1]+=deg[i];
    }
    if(deg[v.size()-1]!=-1)return 1;
    
    int cnt=0;
    vis[0]=1;
    
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()){
        int x=Q.front();
        cnt++;
        Q.pop();
        for(auto y: a[x]){
            if(!vis[y]){
                vis[y]=1;
                Q.push(y);
            }
        }
    }
    if(cnt==v.size())return 0;
    return 1;
}

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

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if(cnt==v.size())return 0;
      |        ~~~^~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36