제출 #319739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319739		Everule	자매 도시 (APIO20_swap)	C++17	0 / 100	152 ms	24164 KiB

swap

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
template<typename T>
ostream& operator+(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out<<x<<" ";
    }
    out<<"\n";
    return out;
}
template<typename T>
ostream& operator*(ostream& out, const vector<T> &vec){
    for(const auto &x : vec){
        out+x;
    }
    return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T> &vec){
    for(auto &x : vec){
        in>>x;
    }
    return in;
}
struct Persistent_DSU{
    int n;
    vector<int> par;
    vector<int> partime;
    struct state{
        int edges, size, time;
        state(int edges, int size,int time) : edges(edges), size(size), time(time) {}
        state() {}
        bool operator<(const state &o){
            return time<o.time;
        }
        bool operator<(int t){
            return time < t;
        }
    };
    vector<vector<state>> sz;
    int currtime = 0;
    Persistent_DSU(int n) : n(n){
        par.resize(n);
        iota(par.begin(), par.end(), 0);
        partime.assign(n, -1);
        sz.assign(n, {state(0,1,0)});
    }
    int find_set(int u,int t){
        while(par[u] != u && partime[u] < t){
            u = par[u];
        }
        return u;
    }
    void join_sets(int u,int v){
        int r1 = find_set(u, currtime);
        int r2 = find_set(v, currtime);
        if(r1 == r2){
            auto s = sz[r1].back();
            s.edges++;
            s.time = currtime;
            sz[r1].push_back(s);
            ++currtime;
            return;
        }
        auto [e1,s1,t1] = sz[r1].back();
        auto [e2,s2,t2] = sz[r2].back();
        if(s1 > s2){
            swap(r1,r2);
        }
        par[r1] = r2;
        partime[r1] = currtime;
        sz[r2].push_back(state(e1+e2+1,s1+s2,currtime));
        ++currtime;
    }
    state findstate(int u,int t){
        auto it = lower_bound(sz[u].begin(), sz[u].end(), t);
        --it;
        return (*it);
    }
};
const int INF = 1e9;
struct Edge{
    int u,v,w;
    Edge(int u,int v,int w) : u(u), v(v), w(w) {}
    Edge() {}
    bool operator<(const Edge &o){
        return w < o.w;
    }
};
Persistent_DSU dsu(0);
vector<Edge> edges;
void init(int n,int m, vector<int> u, vector<int> v, vector<int> w){
    edges.resize(m);
    dsu = Persistent_DSU(n);
    for(int i=0;i<m;i++){
        edges[i] = Edge(u[i],v[i],w[i]);
    }
    Persistent_DSU dsu(n);
    sort(edges.begin(), edges.end());
    for(const auto &[u,v,w] : edges){
        dsu.join_sets(u,v);
    }
}
int getMinimumFuelCapacity(int x,int y){
    int mn = 1, mx = edges.size() + 1;
    while(mn < mx){
        int mid = mn + mx;
        mid>>=1;
        int r1 = dsu.find_set(x, mid);
        int r2 = dsu.find_set(y, mid);
        if(r1 != r2){
            mn = mid + 1;
            continue;
        }
        auto s = dsu.findstate(r1, mid);
        if(s.edges < s.size){
            mn = mid + 1;
        }
        else{
            mx = mid;
        }
    } 
    if(mn == edges.size() + 1) return -1;
    return edges[mn-1].w;
}

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

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:126:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     if(mn == edges.size() + 1) return -1;
      |        ~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27