제출 #1316176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316176		kindep	Dreaming (IOI13_dreaming)	C++20	0 / 100	70 ms	18388 KiB

dreaming

//Dreaming
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int MAX_N=1e5+9, LOG=18, INF=1e9;
vector<pair<int, int>> drzewo[MAX_N];
bool odw[MAX_N];
int jump[MAX_N][LOG], odl[MAX_N], korzen[MAX_N], gl[MAX_N], maksodl, a, minodl=INF;
pair<int, int> sred[MAX_N], maks[MAX_N];

void dfs(int w, int ojc=0){
    jump[w][0]=ojc;
    gl[w]=gl[ojc]+1;
    for (int i=1; i<LOG; i++)
        jump[w][i]=jump[jump[w][i-1]][i-1];
    odw[w]=true;
    for (auto [new_w, c]:drzewo[w]){
        if (!odw[new_w]){
            odl[new_w]=odl[w]+c;
            if (maksodl<odl[new_w])
                maksodl=odl[new_w], a=new_w;
            dfs(new_w, w);
        }
    }
}

void dfs2(int w, int akt=0, int ojc=0){
    if (akt>maksodl)
        maksodl=akt, a=w;
    for (auto [new_w, c]:drzewo[w])
        if (new_w!=ojc)
            dfs2(new_w, akt+c, w);
}

int lca(int x, int y){
    if (gl[x]<gl[y])
        swap(x, y);
    for (int i=LOG-1; i>=0; i--)
        if ((gl[x]-gl[y])>=(1<<i))
            x=jump[x][i];
    if (x==y)
        return x;
    for (int i=LOG-1; i>=0; i--)
        if (jump[x][i]!=jump[y][i])
            x=jump[x][i], y=jump[y][i];
    return jump[x][0];
}

void znajdz_korzen(int w, pair<int, int> x, int ojc=0){
    int nowa=max(odl[w]+odl[x.first]-2*odl[lca(w, x.first)], odl[w]+odl[x.second]-2*odl[lca(w, x.second)]);
    if (nowa<minodl)
        minodl=nowa, a=w;
    for (auto [new_w, c]:drzewo[w])
        if (new_w!=ojc)
            znajdz_korzen(new_w, x, w);
}

void ustaw_korzen(int w, int k, int ojc=0){
    korzen[w]=k;
    for (auto [new_w, c]:drzewo[w])
        if(new_w!=ojc)
            ustaw_korzen(new_w, k, w);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for (int i=0; i<M; i++)
        drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]});
    /*
    int b, c;
    for (int i=0; i<M; i++)
        cin >> a >> b >> c, drzewo[a+1].push_back({b+1, c}), drzewo[b+1].push_back({a+1, c});
    */
    vector<int> spojne;
    for (int i=1; i<=N; i++){
        if (!odw[i]){
            maksodl=0, a=i;
            dfs(i);
            sred[i].first=a;
            maksodl=0, a=i;
            dfs2(sred[i].first);
            sred[i].second=a;
            minodl=INF, a=i;
            znajdz_korzen(i, sred[i]);
            ustaw_korzen(i, a);
            sred[a]=sred[i];
            maks[a].first=odl[sred[a].first]+odl[a]-2*odl[lca(a, sred[a].first)], maks[a].second=odl[sred[a].second]+odl[a]-2*odl[lca(a, sred[a].second)];
            if (maks[a].first<maks[a].second)
                swap(maks[a].first, maks[a].second);
            spojne.push_back(a);
        }
    }
    int wyn=maks[spojne[0]].first+maks[spojne[0]].second;
    for (int i=1; i<spojne.size(); i++){
        int a1=maks[spojne[i-1]].first, a2=maks[spojne[i-1]].second, b1=maks[spojne[i]].first, b2=maks[spojne[i]].second;
        if (a1==b1){
            if (b2<a2)
                b1+=L, b2+=L;
            else
                a1+=L, a2+=L;
        }
        else if (b1<a1)
            b1+=L, b2+=L;
        else
            a1+=L, a2+=L;
        vector<int> pom; pom.push_back(a1), pom.push_back(a2), pom.push_back(b1), pom.push_back(b2);
        sort(pom.begin(), pom.end());
        maks[spojne[i]].first=pom[3], maks[spojne[i]].second=pom[2];
        wyn=max(wyn, maks[spojne[i]].first+maks[spojne[i]].second);
    }
    return wyn;
}

/*
int main(){
    int n, m, l; cin >> n >> m >> l;
    cout << travelTime(n, m, l);
}
*/

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