Submission #556508

#	Time	Username	Problem	Language	Result	Execution time	Memory
556508		n0sk1ll	Dreaming (IOI13_dreaming)	C++17	18 / 100	59 ms	14416 KiB

dreaming

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

using namespace std;

vector<vector<pair<int,int>>> g(100005);
int rv[5],dub[100005];
bitset<100005> vis;

int dalj(int p, int q, int wq)
{
    int ret=p; dub[p]=dub[q]+wq;
    for (auto [it,w] : g[p]) if (it!=q)
    {
        int tmp=dalj(it,p,w);
        if (dub[tmp]>dub[ret]) ret=tmp;
    }
    return ret;
}

bool naso;
vector<int> path;
void put(int p, int q, int wq, int s)
{
    if (!naso) path.push_back(wq);
    if (p==s) naso=true;
    for (auto [it,w] : g[p]) if (it!=q) put(it,p,w,s);
    if (!naso) path.pop_back();
}

void dfs(int p, int q)
{
    vis[p]=1;
    for (auto [it,w] : g[p]) if (it!=q) dfs(it,p);
}

vector<int> niz;

int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
    dub[-1]=-1;

    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]});
    for (int i=0;i<n;i++) if (!vis[i])
    {
        int a=dalj(i,-1,0),b=dalj(a,-1,0);
        naso=false,path.clear(),put(a,-1,0,b);

        int s=0;
        for (auto it : path) s+=it;
        int tmp=0;
        for (auto it : path)
        {
            tmp+=it;
            if (2*tmp>=s)
            {
                niz.push_back(min(tmp,s+it-tmp));
                break;
            }
        }

        dfs(i,-1);
    }

    //for (auto it : niz) cout<<it<<" "; cout<<endl;
    sort(niz.begin(),niz.end(),greater<int>());
    if (niz.size()==1) return niz[0];
    if (niz.size()==2) return niz[0]+niz[1]+L;
    return max(niz[0]+niz[1]+L,niz[1]+niz[2]+2*L);
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:41:11: warning: array subscript -1 is below array bounds of 'int [100005]' [-Warray-bounds]
   41 |     dub[-1]=-1;
      |     ~~~~~~^
dreaming.cpp:7:11: note: while referencing 'dub'
    7 | int rv[5],dub[100005];
      |           ^~~

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