Submission #776268

#	Time	Username	Problem	Language	Result	Execution time	Memory
776268		kirakaminski968	Dreaming (IOI13_dreaming)	C++17	100 / 100	90 ms	14952 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 1e5+5;
int n,m,l;
bool vis[MAXN], vis2[MAXN];
vector<pair<int,int>> adj[MAXN]; //first node, then distance
pair<int,int> dijkstra_longest(bool *visited, int src){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,src}); int maxn = -1, maxnode = -1; visited[src] = true; 
    while(!pq.empty()){
        int u = pq.top().second, cdist = pq.top().first; pq.pop();
        if(cdist > maxn){
            maxn = cdist;
            maxnode = u;
        }
        for(auto p : adj[u]){
            if(!visited[p.first]){
                visited[p.first] = true; 
                pq.push({cdist+p.second,p.first});
            }
        }
    }
    return {maxn,maxnode};
}
int get_length(int x){ //returns the longest length in the component
    pair<int,int> res = dijkstra_longest(vis2,x);
    return dijkstra_longest(vis,res.second).first;
}
int ret,len;
bool dfs(int cur, int f, int p, int di){
    if(cur == f) return true;
    for(auto v : adj[cur]){
        if(v.first != p){
            if(dfs(v.first,f,cur,di+v.second)){
                ret = min(ret,max(len-di,di));
                return true;
            }
        }
    }
    return false;
}
int get_diameter(int x){
    pair<int,int> res = dijkstra_longest(vis2,x);
    pair<int,int> newres = dijkstra_longest(vis,res.second);
    len = newres.first; ret = len;
    dfs(res.second,newres.second,-1,0);
    return ret;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){ //L is the length of new trails, A and B are the endpoints of a trail; T is the length of it
    n = N; m = M; l = L;
    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]});
    }
    int ans = 0;
    for(int i = 0;i<N;++i){
        if(!vis[i]) ans = max(ans,get_length(i));
    }
    memset(vis,false,sizeof(vis)); memset(vis2,false,sizeof(vis2));
    vector<int> results;
    for(int i = 0;i<N;++i){
        if(!vis[i]) results.push_back(get_diameter(i));
    }
    sort(results.rbegin(),results.rend());
    if(results.size() > 1){
        ans = max(ans,results[0]+results[1]+L);
    }
    if(results.size() > 2){
        ans = max(ans,results[1]+results[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