Submission #1184418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184418		ivaziva	Dreaming (IOI13_dreaming)	C++20	100 / 100	81 ms	21000 KiB

dreaming

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

using namespace std;

#define MAXN 100001

long long brkomp=0,timer=1,slucaj=0;
vector<pair<long long,long long>> adj[MAXN];
long long komponenta[MAXN],dist[MAXN],broj[MAXN];
vector<long long> nodes[MAXN];
vector<long long> answers;

void dfs(long long node,long long pret)
{
    komponenta[node]=brkomp;nodes[brkomp].push_back(node);
    for (pair<long long,long long> par:adj[node])
    {
        int sled=par.first,w=par.second;if (sled==pret) continue;
        dist[sled]=dist[node]+w;dfs(sled,node);
    }
}

void dfs1(long long node,long long pret)
{
    for (pair<long long,long long> par:adj[node])
    {
        int sled=par.first,w=par.second;if (sled==pret) continue;
        dist[sled]=dist[node]+w;dfs1(sled,node);
    }
}

void dfs2(long long node,long long pret,long long val)
{
    if (dist[node]==val) broj[node]=1;
    for (pair<long long,long long> par:adj[node])
    {
        long long sled=par.first,w=par.second;if (sled==pret) continue;
        dfs2(sled,node,val);broj[node]+=broj[sled];
    }
}

void resi(long long komp)
{
    long long maxdist=0,maxnode=nodes[komp][0];
    for (long long node:nodes[komp])
    {
        if (dist[node]>maxdist) {maxdist=dist[node];maxnode=node;}
    }
    dist[maxnode]=0;dfs1(maxnode,0);long long len=0;
    for (long long node:nodes[komp]) len=max(len,dist[node]);
    slucaj=max(slucaj,len);long long sol=len;dfs2(maxnode,0,len);
    for (int node:nodes[komp])
    {
        if (broj[node]!=0) sol=min(sol,max(dist[node],len-dist[node]));
    }
    answers.push_back(sol);
}

int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
    for (long long i=0;i<m;i++) {long long node1=a[i]+1,node2=b[i]+1,weight=t[i];adj[node1].push_back({node2,weight});adj[node2].push_back({node1,weight});}
    for (long long node=1;node<=n;node++)
    {
        if (komponenta[node]==0) {brkomp++;dfs(node,0);}
    }
    for (long long komp=1;komp<=brkomp;komp++) resi(komp);
    sort(answers.begin(),answers.end());reverse(answers.begin(),answers.end());long long ans=slucaj;
    if (answers.size()==1) ans=max(ans,answers[0]);
    if (answers.size()>=2) ans=max(ans,answers[0]+answers[1]+l);
    if (answers.size()>=3) ans=max(ans,answers[1]+answers[2]+2*l);
    return ans;
}

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