oj.uz

Submission #776266

# Submission time Handle Problem Language Result Execution time Memory
776266 2023-07-07T14:07:18 Z kirakaminski968 Dreaming (IOI13_dreaming) C++17
18 / 100
 38 ms 9804 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 *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; vis[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
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 38 ms 9804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5512 KB Output is correct
2 Correct 27 ms 5980 KB Output is correct
3 Correct 25 ms 5960 KB Output is correct
4 Correct 25 ms 5880 KB Output is correct
5 Correct 26 ms 5864 KB Output is correct
6 Correct 32 ms 6392 KB Output is correct
7 Correct 32 ms 6100 KB Output is correct
8 Correct 31 ms 5912 KB Output is correct
9 Correct 24 ms 5816 KB Output is correct
10 Correct 28 ms 6076 KB Output is correct
11 Correct 1 ms 2772 KB Output is correct
12 Correct 13 ms 3420 KB Output is correct
13 Correct 16 ms 3552 KB Output is correct
14 Correct 13 ms 3536 KB Output is correct
15 Correct 18 ms 3520 KB Output is correct
16 Correct 13 ms 3504 KB Output is correct
17 Correct 13 ms 3456 KB Output is correct
18 Correct 13 ms 3536 KB Output is correct
19 Correct 14 ms 3408 KB Output is correct
20 Correct 1 ms 2772 KB Output is correct
21 Correct 1 ms 2784 KB Output is correct
22 Correct 2 ms 2796 KB Output is correct
23 Correct 13 ms 3420 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 38 ms 9804 KB Output isn't correct
2 Halted 0 ms 0 KB -