Submission #979561

#	Time	Username	Problem	Language	Result	Execution time	Memory
979561		vjudge1	Swapping Cities (APIO20_swap)	C++17	0 / 100	97 ms	14276 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N =3e5 + 9 , mod = 1e9 + 7;
ll  p[N][3] , sz[N]  ;

vector<pair<ll,ll>>vv;
int get(int x , vector<pair<ll,ll>>&vv ){
    if(vv.size())
        vv.pb({x , p[x][1] });
    return (p[x][0] == x ? x : get(p[x][0] , vv));
}
void join(int x , int y , ll k){
    x = get(x , vv) , y = get(y , vv);
    if(x != y){
        if(sz[x] < sz[y])
            swap(x , y);
        p[y][0] = x;
        p[y][1] = k;
        p[x][2] = min(p[y][2] , p[x][2]);
        sz[x] += sz[y];
    }else {
        p[y][2] = min(p[y][2] , k);
    }
}
void init(int n , int m , vector<int>v , vector<int>u , vector<int>c)
{
    vector<pair<ll,pair<ll,ll>>>vc;
    for(int i = 0; i <= n; i++)
        p[i][0] =  i , p[i][1] = 0, p[i][2] = 1e18 , sz[i] = 1;
    for(int i = 0; i < m; i++)
        vc.pb({c[i] , {v[i] + 1, u[i] + 1}});
    sort(all(vc));
    for(auto to : vc){
        join(to.se.fi , to.se.se , to.fi);
    }
}

int getMinimumFuelCapacity(int l, int r) {
        l++;
        r++;

        vector<pair<ll,ll>>v1 = {{0 , 0}}, v2= {{-1 , 0}};
        get(l , v1);
        get(r , v2);
        ll x = v1.size() - 1,  y =  v2.size() - 1;
        ll mx = 0 , mn = 1e18;
        while(1){
            mn = min({mn , max(v1[x].se , p[v1[x].fi][2] )});
            mn = min({mn , max(v1[y].se , p[v1[y].fi][2] )});
            if(v1[x].fi != v2[y].fi){
                mx = max({mx , v1[x].se , v2[y].se });
                break;
            }
            x-- , y--;
        }
        mx = max(mx , mn);
        while(1){
            if(v1[x].fi != v2[y].fi){
                mx = max({mx , v1[x].se , v2[y].se });
                break;
            }
            x-- , y--;
        }
        if(mx == 1e18)
            mx = -1;
        return mx;
	return mx;
}
/*
int main(){
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout<<getMinimumFuelCapacity(1,2)<<"\n";
    cout<<getMinimumFuelCapacity(2,4)<<"\n";
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
}*/

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