Submission #351209

#	Time	Username	Problem	Language	Result	Execution time	Memory
351209		Tony1234	Dreaming (IOI13_dreaming)	C++14	100 / 100	136 ms	12652 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef pair<int, int> pii;
const int MM = 100010;
vector<pii> adj[MM];
bool vis[MM];
int dis[MM];
vector<int> diam;
int furthest = 0, cit = -1;
void dfs(int src, int cost, int prev){
   if(cost > furthest){
    furthest = cost;
    cit = src;
   }
   if(dis[src] < cost){
    dis[src] = cost;
   }
   vis[src] = true;
   for(pii i: adj[src]){
    if(i.first != prev){
        dfs(i.first, cost+i.second, src);
    }
   }
}
int ans = 100000000;
void dfs2(int src, int prev, int c){
    ans = min(ans, dis[src]);
    for(pii u: adj[src]){
        if(u.first!=prev){
            dfs2(u.first, src, u.second + c);
        }
    }

}
int radius(int src){
    dfs(src, 0, -1);
    int i = cit;
    cit = -1; furthest = 0;
    dfs(i,0, -1);
    int gg = cit;
   cit = -1; furthest = 0;
    dfs(gg,0,-1);
    diam.push_back(furthest);
    dfs2(gg, -1, 0);
    int ss = ans;
    ans = 100000000;
    cit = -1; furthest = 0;
    return ss;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]){

    for(int i=0; i < M; i++){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    vector<int>  radii;
    for(int i=0; i < N; i++){
        if(!vis[i]){
           radii.push_back(radius(i));

        }
    }
    int ans = 0;
    sort(radii.begin(), radii.end());
    reverse(radii.begin(), radii.end());
    if(radii.size() >= 2){
        ans = max(ans, radii[0]+radii[1]+L);

    }
    if(radii.size() >= 3){
        ans = max(ans, radii[1]+radii[2]+L+L);
    }
    for(int i: diam){
        ans = max(ans, i);
    }
    return ans;


}



/*int a[MM], b[MM], c[MM];
int main(){
    int n, m, l;
     cin >> n >> m >> l;
     for(int i=0; i < m; i++){
        int x, y, z; cin >> x >> y >> z;
        a[i] = x; b[i] = y; c[i] = z;
     }
     cout << travelTime(n, m, l, a, b, c) << '\n';
 return 0;
}
*/

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