Submission #1033537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033537		ezzzay	Dreaming (IOI13_dreaming)	C++14	0 / 100	1063 ms	16596 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
const int MN=3e5+5;;
vector<pair<int,int>>v[MN];
bool vis[MN];
int dist[MN];
vector<int>tmp;
void df(int a){
    vis[a]=1;
    tmp.pb(a);
    for(auto p:v[a]){
        if(vis[p.ff]==0)df(p.ff);
    }
}
vector<int>vh;
int z=0;
void dfs(int a, int u){
    for(auto p:v[a]){
        int b=p.ff;
        int c=p.ss;
        if(b==u)continue;
        dist[b]=dist[a]+c;
        z=max(z,dist[b]);
        dfs(b,a);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<N;i++)vis[i]=0;
    for(int i=0;i<M;i++){
        v[A[i]].pb({B[i],T[i]});
        v[B[i]].pb({A[i],T[i]});
    }
    vector<int>vec;
    for(int i=0;i<N;i++){
        if(vis[i]==0){
           
            tmp.clear();
            df(i);
            int g=1e9;
            for(auto a:tmp){
                for(int j=0;j<N;j++){
                    dist[j]=0;
                }
                vh.clear();
                z=0;
                dfs(a,-1);
                g=min(g,z);
            }
            vec.pb(g);
        }
    }
    sort(vec.begin(),vec.end(),greater<int>());
    if(vec.size()==2){
        return vec[0]+vec[1]+L;
    }
    else{
        return max(vec[0]+vec[1]+L,vec[1]+vec[2]+L*2);
    }
}

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