oj.uz

Submission #776260

# Submission time Handle Problem Language Result Execution time Memory
776260 2023-07-07T14:02:21 Z kirakaminski968 Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 12528 KB 
#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 *vis, int src){
    vector<int> dist(n,-1);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[src] = 0; pq.push({src,0}); int maxn = -1, maxnode = -1;
    while(!pq.empty()){
        int u = pq.top().first, cdist = pq.top().second; pq.pop();
        vis[u] = true;
        if(cdist > maxn){
            maxn = cdist;
            maxnode = u;
        }
        for(auto p : adj[u]){
            if(dist[p.first] == -1){
                dist[p.first] = cdist+p.second;
                pq.push({dist[p.first],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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 574 ms 12528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 574 ms 12528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 6012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 574 ms 12528 KB Output isn't correct
2 Halted 0 ms 0 KB -