oj.uz

Submission #819996

# Submission time Handle Problem Language Result Execution time Memory
819996 2023-08-10T17:20:45 Z annabeth9680 Dreaming (IOI13_dreaming) C++17
14 / 100
 43 ms 13676 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12360 KB Output is correct
2 Correct 41 ms 13676 KB Output is correct
3 Correct 27 ms 10084 KB Output is correct
4 Correct 7 ms 4468 KB Output is correct
5 Correct 5 ms 3668 KB Output is correct
6 Correct 11 ms 5204 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 27 ms 6712 KB Output is correct
9 Correct 26 ms 8128 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 37 ms 9884 KB Output is correct
12 Correct 43 ms 11640 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 1 ms 2772 KB Output is correct
12 Correct 1 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2788 KB Output is correct
15 Incorrect 2 ms 2772 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12360 KB Output is correct
2 Correct 41 ms 13676 KB Output is correct
3 Correct 27 ms 10084 KB Output is correct
4 Correct 7 ms 4468 KB Output is correct
5 Correct 5 ms 3668 KB Output is correct
6 Correct 11 ms 5204 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 27 ms 6712 KB Output is correct
9 Correct 26 ms 8128 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 37 ms 9884 KB Output is correct
12 Correct 43 ms 11640 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 1 ms 2772 KB Output is correct
15 Correct 2 ms 2784 KB Output is correct
16 Correct 1 ms 2772 KB Output is correct
17 Correct 1 ms 2772 KB Output is correct
18 Correct 1 ms 2772 KB Output is correct
19 Correct 2 ms 2772 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 1 ms 2772 KB Output is correct
22 Correct 2 ms 2900 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 1 ms 2772 KB Output is correct
25 Correct 1 ms 2772 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 1 ms 2788 KB Output is correct
28 Incorrect 2 ms 2772 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5536 KB Output is correct
2 Correct 23 ms 5996 KB Output is correct
3 Correct 30 ms 5892 KB Output is correct
4 Correct 23 ms 5964 KB Output is correct
5 Correct 24 ms 5956 KB Output is correct
6 Correct 24 ms 6416 KB Output is correct
7 Correct 24 ms 6064 KB Output is correct
8 Correct 28 ms 5940 KB Output is correct
9 Correct 23 ms 5840 KB Output is correct
10 Correct 24 ms 6068 KB Output is correct
11 Correct 1 ms 2780 KB Output is correct
12 Correct 12 ms 3424 KB Output is correct
13 Correct 13 ms 3540 KB Output is correct
14 Correct 16 ms 3408 KB Output is correct
15 Correct 12 ms 3536 KB Output is correct
16 Correct 13 ms 3504 KB Output is correct
17 Correct 12 ms 3408 KB Output is correct
18 Correct 13 ms 3556 KB Output is correct
19 Correct 12 ms 3420 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Incorrect 1 ms 2772 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2784 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2772 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 1 ms 2772 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 1 ms 2772 KB Output is correct
12 Correct 1 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2788 KB Output is correct
15 Incorrect 2 ms 2772 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12360 KB Output is correct
2 Correct 41 ms 13676 KB Output is correct
3 Correct 27 ms 10084 KB Output is correct
4 Correct 7 ms 4468 KB Output is correct
5 Correct 5 ms 3668 KB Output is correct
6 Correct 11 ms 5204 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 27 ms 6712 KB Output is correct
9 Correct 26 ms 8128 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct
11 Correct 37 ms 9884 KB Output is correct
12 Correct 43 ms 11640 KB Output is correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 1 ms 2772 KB Output is correct
15 Correct 2 ms 2784 KB Output is correct
16 Correct 1 ms 2772 KB Output is correct
17 Correct 1 ms 2772 KB Output is correct
18 Correct 1 ms 2772 KB Output is correct
19 Correct 2 ms 2772 KB Output is correct
20 Correct 2 ms 2772 KB Output is correct
21 Correct 1 ms 2772 KB Output is correct
22 Correct 2 ms 2900 KB Output is correct
23 Correct 2 ms 2772 KB Output is correct
24 Correct 1 ms 2772 KB Output is correct
25 Correct 1 ms 2772 KB Output is correct
26 Correct 2 ms 2772 KB Output is correct
27 Correct 1 ms 2788 KB Output is correct
28 Incorrect 2 ms 2772 KB Output isn't correct
29 Halted 0 ms 0 KB -