oj.uz

Submission #430655

# Submission time Handle Problem Language Result Execution time Memory
430655 2021-06-16T18:03:38 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
18 / 100
 574 ms 17572 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e5 + 7;

int val,ve;
bool used[maxN];
vector<pair<int, int>> v[maxN];

void dfs(int x, int p, int sum)
{
        used[x] = true;
        if(sum >= val){
                val = sum;
                ve = x;
        }
        for(auto y : v[x]){
                if(y.first != p){
                        dfs(y.first, x, sum + y.second);
                }
        }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
        for(int i = 0; i < M; i++){
                v[A[i]].push_back({B[i], T[i]});
                v[B[i]].push_back({A[i], T[i]});
        }
        vector<int> p(N, -1);
        vector<int> d(N, 1e9);
        vector<pair<int, int>> X;
        for(int i = 0; i < N; i++){
                if(!used[i]){
                        val = ve = 0;
                        dfs(i, i, 0);
                        int r1 = ve;
                        val = ve = 0;
                        dfs(r1, r1, 0);
                        int r2 = ve;
                        queue<int> q;
                        q.push(r1);
                        d[r1] = 0;
                        while(!q.empty()){
                                int x = q.front();
                                q.pop();
                                for(auto y : v[x]){
                                        if(d[y.first] == 1e9){
                                                d[y.first] = d[x] + 1;
                                                p[y.first] = x;
                                                q.push(y.first);
                                        }
                                }
                        }
                        vector<int> pa;
                        while(r2 != r1){
                                pa.push_back(r2);
                                r2 = p[r2];
                        }
                        pa.push_back(r1);
                        int v1 = 0;
                        int res = 1e9;
                        for(int j = max(0, (int)pa.size() / 2 - 2); j < min((int)pa.size(), (int)pa.size() / 2 + 2); j++){
                                int st = pa[j];
                                queue<int> q;
                                q.push(st);
                                map<int, int> d;
                                int mx = 0;
                                d[st] = 0;
                                while(!q.empty()){
                                        int x = q.front();
                                        q.pop();
                                        for(auto y : v[x]){
                                                if(d.find(y.first) == d.end()){
                                                        d[y.first] = d[x] + y.second;
                                                        q.push(y.first);
                                                        mx = max(mx, d[x] + y.second);
                                                }
                                        }
                                }
                                if(mx < res){
                                        res = mx;
                                        v1 = st;
                                }
                        }
                        X.push_back({res, v1});
                }
        }
        sort(X.rbegin(), X.rend());
        for(int i = 1; i < (int)X.size(); i++){
                v[X[0].second].push_back({X[i].second, L});
                v[X[i].second].push_back({X[0].second, L});
        }
        val = ve = 0;
        dfs(0, 0, 0);
        val = 0;
        dfs(ve, ve, 0);
        return val;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 16180 KB Output is correct
2 Correct 498 ms 17572 KB Output is correct
3 Correct 263 ms 12504 KB Output is correct
4 Correct 47 ms 4808 KB Output is correct
5 Correct 32 ms 3784 KB Output is correct
6 Correct 76 ms 5892 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 161 ms 7680 KB Output is correct
9 Correct 230 ms 9872 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 345 ms 11980 KB Output is correct
12 Correct 434 ms 14572 KB Output is correct
13 Incorrect 4 ms 2764 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2592 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 16180 KB Output is correct
2 Correct 498 ms 17572 KB Output is correct
3 Correct 263 ms 12504 KB Output is correct
4 Correct 47 ms 4808 KB Output is correct
5 Correct 32 ms 3784 KB Output is correct
6 Correct 76 ms 5892 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 161 ms 7680 KB Output is correct
9 Correct 230 ms 9872 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 345 ms 11980 KB Output is correct
12 Correct 434 ms 14572 KB Output is correct
13 Incorrect 4 ms 2764 KB Output isn't correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7700 KB Output is correct
2 Correct 85 ms 7784 KB Output is correct
3 Correct 61 ms 7664 KB Output is correct
4 Correct 69 ms 7760 KB Output is correct
5 Correct 60 ms 7684 KB Output is correct
6 Correct 77 ms 8512 KB Output is correct
7 Correct 77 ms 8064 KB Output is correct
8 Correct 61 ms 7556 KB Output is correct
9 Correct 71 ms 7556 KB Output is correct
10 Correct 67 ms 7888 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 42 ms 8224 KB Output is correct
13 Correct 44 ms 8156 KB Output is correct
14 Correct 42 ms 8264 KB Output is correct
15 Correct 40 ms 8116 KB Output is correct
16 Correct 43 ms 8216 KB Output is correct
17 Correct 42 ms 8180 KB Output is correct
18 Correct 41 ms 8120 KB Output is correct
19 Correct 42 ms 8224 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 4 ms 2764 KB Output is correct
23 Correct 49 ms 8108 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2592 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 16180 KB Output is correct
2 Correct 498 ms 17572 KB Output is correct
3 Correct 263 ms 12504 KB Output is correct
4 Correct 47 ms 4808 KB Output is correct
5 Correct 32 ms 3784 KB Output is correct
6 Correct 76 ms 5892 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 161 ms 7680 KB Output is correct
9 Correct 230 ms 9872 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 345 ms 11980 KB Output is correct
12 Correct 434 ms 14572 KB Output is correct
13 Incorrect 4 ms 2764 KB Output isn't correct