제출 #1030689

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030689		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	447 ms	42404 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
#include "railroad.h"
int rev[500100],par[500100],prf[500100];
int abp(int n){
    return par[n]?par[n]=abp(par[n]):n;
}
bool merge(int a,int b){
    a=abp(a),b=abp(b);
    if(a-b)return par[a]=b;
    return 0;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    map<int,int>mp;
    s.push_back(1e9);
    t.push_back(1);
    for(auto i:s) mp[i];
    for(auto i:t) mp[i];
    int CC=0;
    for(auto&[i,j]:mp)
        rev[j=++CC]=i;
    long long ans=0;
    for(int i=0;i<=n;i++){
        s[i]=mp[s[i]];
        t[i]=mp[t[i]];
        merge(s[i],t[i]);
        prf[s[i]]++;
        prf[t[i]]--;
    }
    for(int i=1;i<CC;i++) {
        prf[i]+=prf[i-1];
        if(prf[i]){
            merge(i,i+1);
            if(prf[i]>0)
                ans+=prf[i]*(long long)(rev[i+1]-rev[i]);
        }
    }
    vector<tuple<int,int,int>> v;
    for(int i=2;i<=CC;i++)
        v.push_back({rev[i]-rev[i-1],i,i-1});
    sort(v.begin(),v.end());
    for(auto[w,a,b]:v)
        if(merge(a,b))
            ans+=w;
    return ans;
}

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

railroad.cpp: In function 'bool merge(int, int)':
railroad.cpp:10:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   10 |     if(a-b)return par[a]=b;
      |                   ~~~~~~^~

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