Submission #1258329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258329		Szymon_Pilipczuk	Dreaming (IOI13_dreaming)	C++20	18 / 100	35 ms	14656 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int d[100000];
int mxd[100000];
bool vis[100000];
vector<vector<pair<int,int>>> gr;
void cd(int v)
{
    //cerr<<v<<"\n";
    vis[v] = true;
    for(pair<int,int> i : gr[v])
    {
        if(!vis[i.st])
        {
            cd(i.st);
            mxd[v] = max(mxd[v], i.nd + mxd[i.st]);
        }
    }
}
int mx;
void dfs(int v,int md)
{
    if(v == -1)
    {
        return;
    }
    vis[v] = true;
    vector<pair<int,int>> vv;
    for(pair<int,int> i : gr[v])
    {
        if(!vis[i.st])
        {
            vv.pb({mxd[i.st] + i.nd,i.st});
        }
    }
    sort(all(vv));
    reverse(all(vv));
    vv.pb({0,-1});
    mx = min(mx,max(md,vv[0].st));
    for(int i = 1;i<gr[v].size();i++)
    {
        dfs(vv[i].nd,max(md,vv[0].st) + vv[i].st - mxd[vv[i].nd]);
    }
    if(vv[0].nd != -1) dfs(vv[0].nd,max(md,vv[1].st) + vv[0].st - mxd[vv[0].nd]);
}
int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
    gr.resize(n);
    rep(i,m)
    {
        gr[a[i]].pb({b[i],t[i]});
        gr[b[i]].pb({a[i],t[i]});
    }
    rep(i,n)
    {
        if(!vis[i])
        {
            cd(i);
        }
    }
    vector<int> aa;
    rep(i,n) vis[i] = false;
    rep(i,n)
    {
        if(!vis[i])
        {
            mx = inf;
            dfs(i,0);
            aa.pb(mx);
        }
    }
    sort(all(aa));
    reverse(all(aa));
    //rep(i,aa.size()) cerr<<aa[i]<<"\n";
    if(aa.size() == 1)
    {
        return aa[0];
    }
    else if(aa.size() == 2)
    {
        return aa[0] + aa[1] + l;
    }
    else
    {
        return max(aa[0] + aa[1] + l, aa[1] + aa[2] + l * 2);
    }

     
}

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