Submission #1316171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316171		kindep	꿈 (IOI13_dreaming)	C++20	Compilation error	0 ms	0 KiB

dreaming

//Dreaming
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int MAX_N=1e5+9, LOG=17, 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){
    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]});
    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;
        if (a1>b1)
            maks[spojne[i]]=make_pair(a1, max(b1, a2));
        else
            maks[spojne[i]]=make_pair(b1, max(b2, a1));
        wyn=max(wyn, maks[spojne[i]].first+maks[spojne[i]].second);
    }
    return wyn;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int)':
dreaming.cpp:67:16: error: 'A' was not declared in this scope
   67 |         drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]});
      |                ^
dreaming.cpp:67:35: error: 'B' was not declared in this scope
   67 |         drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]});
      |                                   ^
dreaming.cpp:67:43: error: 'T' was not declared in this scope
   67 |         drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]});
      |                                           ^