Submission #1280945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280945		kiteyu	꿈 (IOI13_dreaming)	C++20	18 / 100	60 ms	18284 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 2e5;
int par[N+5];
vector<pair<int,int>> g[N+5];
bool f[N+5];
ll d[2][N+5];
vector<int> V;
pair<ll,ll> G[N+5];


int fba(int x){
    return par[x] == x ? x : par[x] = fba(par[x]);
}

void join(int x,int y){
    //cout << x << ',' << y << "!\n";
    x = fba(x);
    y = fba(y);
    if(x != y){
        par[y] = x;
    }
}

pair<int,ll> dfs(int x,int p,ll dist,int ty){
    if(ty == 1)
        V.push_back(x);
    pair<int,ll> mx = {x,dist};
    d[ty][x] = dist;
    for(pair<int,int> i : g[x]) if(i.fi != p){
        pair<int,ll> tmp = dfs(i.fi,x,(ll)dist + i.se,ty);
        if(tmp.se > mx.se) mx = tmp;
    }
    return mx;
}

int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for(int i = 0 ; i < n ; ++i) par[i] = i;
    for(int i = 0 ; i <= m ; ++i){

        g[a[i]].push_back({b[i],t[i]});
        g[b[i]].push_back({a[i],t[i]});
        join(a[i],b[i]);
    }
//    cout << fba(1) << ',' << fba(2) << "!\n";
//    cout << "?\n";
    int n1 = 0;
    for(int i = 0 ; i < n ; ++i){
        int pos = fba(i);
        if(f[pos]) continue;
        //cout << i << ',' << pos << ":\n";
        V.clear();
        pair<int,int> t = dfs(pos,pos,0,0);
        pair<int,int> t1 = dfs(t.fi,t.fi,0,1);
        dfs(t1.fi,t1.fi,0,0);
       // cout << t.fi << ' ' << t1.fi <<  ' ' << t1.se << '\n';


        n1++;
        f[pos] = 1;
        G[n1] = {-1,-1};
        for(int j : V){
            int w1 = d[0][j];
            int w2 = d[1][j];

            if(w1 > w2) swap(w1,w2);
            //cout << j << ' ' << w1 << ' ' << w2 << '\n';
            d[0][j] = d[1][j] = 0;
            if(G[n1].se == -1 || G[n1].fi + G[n1].se > w1 + w2 || (w1 + w2 == G[n1].fi + G[n1].se && G[n1].se < w1)) G[n1] = {w2,w1};
        }
        //cout << G[n1].fi << ' ' << G[n1].se << "!\n";
    }
    //cout << "??\n";

    sort(G+1,G+1+n1,greater<pair<ll,ll>>());

//    for(int i = 1 ; i <= n1 ; ++i)
//        cout << G[i].fi << ' ' << G[i].se << "\n";

    pair<ll,ll> mx = G[1];
    for(int i = 2 ; i <= n1 ; ++i){
        if(G[i].fi + l > mx.se){
            mx.se = G[i].fi + l;
            if(mx.se > mx.fi) swap(mx.fi,mx.se);
        }
    }
    return mx.fi + mx.se;
}


//int main(){
//    int n,m,l;
//    cin >> n >> m >> l;
//    int a[m+1],b[m+1],t[m+1];
//    for(int i = 1 ; i <= m ; ++i) cin >> a[i] >> b[i] >> t[i];
//
//    cout << travel_time(n,m,l,a,b,t);
//}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23