Submission #819996

#	Time	Username	Problem	Language	Result	Execution time	Memory
819996		annabeth9680	Dreaming (IOI13_dreaming)	C++17	14 / 100	43 ms	13676 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAXN = 1e5+5;
vector<pair<int,int>> adj[MAXN];
bool visited[MAXN], visited2[MAXN];
pair<int,int> dijkstra(bool *vis, int src){
    int maxn = -1, pos = -1;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,src}); vis[src] = true;
    while(!pq.empty()){
        int u = pq.top().second, cdist = pq.top().first; pq.pop();
        for(auto p : adj[u]){ //first node, then weight
            if(!vis[p.first]){
                vis[p.first] = true;
                pq.push({cdist+p.second,p.first});
                if(cdist+p.second > maxn){
                    maxn = cdist+p.second;
                    pos = p.first;
                }
            }
        }
    }
    return {maxn,pos};
}
int res,laenge;
bool calc(int u, int b, int p, int d){
    if(u == b) return true;
    for(auto v : adj[u]){
        if(v.first != p){
            if(calc(v.first,b,u,d+v.second)){
                res = min(res,max(d,laenge-d));
                return true;
            }
        }
    }
    return false;
}
int get_dia(int x){
    int a = dijkstra(visited2,x).second;
    pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
    res = ret.first; laenge = ret.first;
    calc(a,ret.second,-1,0); //find the smallest value on the path
    //cout << x << " " << res << "\n";
    return res;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    memset(visited,false,sizeof(visited));
    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(!visited[i]){
            int a = dijkstra(visited2,i).second;
            pair<int,int> ret = dijkstra(visited,a); //first is the longest path, second the second node on the longest path
            ans = max(ans,ret.first);
        }
    }
    memset(visited,false,sizeof(visited)); memset(visited2,false,sizeof(visited2));
    vector<int> dias;
    for(int i = 0;i<N;++i){
        if(!visited[i]){
            dias.push_back(get_dia(i));
        }
    }
    sort(dias.rbegin(),dias.rend());
    if(dias.size() > 1){
        ans = max(ans,dias[0]+dias[1]+L);
    }
    if(dias.size() > 2){
        ans = max(ans,dias[1]+dias[2]+2*L);
    }
    return ans;
}

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