제출 #1323540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323540		ZeroCool	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	182 ms	30364 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define int long long
#define ar array
#define all(v) v.begin(), v.end()
using namespace std;

const int INF = 1e9;

struct DSU{
    vector<int> p;
    DSU(int n){
        p.resize(n);
        iota(all(p), 0);
    }

    int fnd(int x){
        if(p[x] == x)return x;
        return p[x] = fnd(p[x]);
    }

    bool upd(int a,int b){
        a = fnd(a);
        b = fnd(b);
        if(a == b)return 0;
        p[a] = b;
        return 1;
    }
};

long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
    s.push_back(INF);
    t.push_back(1);
    int n = (int) s.size();
    map<int,int> mp;
    vector<int> C;
    for(int i = 0;i < n;i++){
        C.push_back(s[i]);
        C.push_back(t[i]);
    }
    sort(all(C));
    C.erase(unique(all(C)), C.end());
    auto comp = [&](int i) -> int{
        return lower_bound(all(C), i) - C.begin();
    };
    DSU dsu(C.size());
    vector<int> v(C.size(), 0);
    for(int i = 0;i < n;i++){
        // cout<<s[i]<<" "<<t[i]<<':';
        s[i] = comp(s[i]);
        t[i] = comp(t[i]);
        // cout<<s[i]<<" "<<t[i]<<'\n';
        dsu.upd(s[i], t[i]);
        v[s[i]]++;
        v[t[i]]--;
    }
    // for(int i = 0;i < n;i++)cout<<v[i]<<" ";
    // cout<<'\n';
    int sum = 0;
    int ans = 0;
    vector<ar<int,3>> e;
    for(int i = 0;i + 1 < v.size();i++){
        sum += v[i];
        if(sum > 0)ans += sum * (C[i + 1] - C[i]);
        if(sum)dsu.upd(i,i + 1);
        e.push_back({C[i + 1] - C[i], i, i + 1});
    }
    sort(all(e));
    for(auto [w, a, b]: e){
        if(dsu.upd(a, b))ans += w;
    }
    return ans;

}

#define int signed

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

railroad.cpp:76: warning: "int" redefined
   76 | #define int signed
      | 
railroad.cpp:3: note: this is the location of the previous definition
    3 | #define int long long
      | 
railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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