Submission #1036962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036962		aaaaaarroz	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	580 ms	42844 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;
    }
     

Compilation message (stderr)

railroad.cpp: In function 'bool merge(int, int)':
railroad.cpp:10:29: 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