Submission #1316247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316247		kindep	Dreaming (IOI13_dreaming)	C++20	100 / 100	97 ms	23120 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;
    int wyn=0;
    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];
            wyn=max(wyn, odl[sred[a].first]+odl[sred[a].second]-2*odl[lca(sred[a].first, sred[a].second)]);
            int pom=max(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)]);
            spojne.push_back(pom);
        }
    }
    sort(spojne.begin(), spojne.end(), greater<int>());
    if (spojne.size()>=3)
        wyn=max(wyn, spojne[1]+2*L+spojne[2]);
    if (spojne.size()>=2)
        wyn=max(wyn, spojne[0]+spojne[1]+L);
    return wyn;
}

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

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