oj.uz

Submission #430667

# Submission time Handle Problem Language Result Execution time Memory
430667 2021-06-16T18:08:55 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
18 / 100
 351 ms 16724 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 - 5); j < min((int)pa.size(), (int)pa.size() / 2 + 5); j++){
                                int st = pa[j];
                                queue<int> q;
                                q.push(st);
                                unordered_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 307 ms 16724 KB Output is correct
2 Correct 280 ms 16680 KB Output is correct
3 Correct 162 ms 11336 KB Output is correct
4 Correct 31 ms 4684 KB Output is correct
5 Correct 25 ms 3660 KB Output is correct
6 Correct 49 ms 5468 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 116 ms 7136 KB Output is correct
9 Correct 148 ms 8876 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 280 ms 11132 KB Output is correct
12 Correct 351 ms 13240 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 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 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 307 ms 16724 KB Output is correct
2 Correct 280 ms 16680 KB Output is correct
3 Correct 162 ms 11336 KB Output is correct
4 Correct 31 ms 4684 KB Output is correct
5 Correct 25 ms 3660 KB Output is correct
6 Correct 49 ms 5468 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 116 ms 7136 KB Output is correct
9 Correct 148 ms 8876 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 280 ms 11132 KB Output is correct
12 Correct 351 ms 13240 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 151 ms 7660 KB Output is correct
2 Correct 115 ms 7784 KB Output is correct
3 Correct 105 ms 7668 KB Output is correct
4 Correct 79 ms 7808 KB Output is correct
5 Correct 89 ms 7636 KB Output is correct
6 Correct 86 ms 8444 KB Output is correct
7 Correct 87 ms 7884 KB Output is correct
8 Correct 76 ms 7684 KB Output is correct
9 Correct 85 ms 7572 KB Output is correct
10 Correct 87 ms 7884 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 56 ms 8152 KB Output is correct
13 Correct 57 ms 8184 KB Output is correct
14 Correct 59 ms 8116 KB Output is correct
15 Correct 56 ms 8168 KB Output is correct
16 Correct 56 ms 8172 KB Output is correct
17 Correct 57 ms 8176 KB Output is correct
18 Correct 64 ms 8112 KB Output is correct
19 Correct 56 ms 8140 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 3 ms 2764 KB Output is correct
23 Correct 58 ms 8236 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 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 307 ms 16724 KB Output is correct
2 Correct 280 ms 16680 KB Output is correct
3 Correct 162 ms 11336 KB Output is correct
4 Correct 31 ms 4684 KB Output is correct
5 Correct 25 ms 3660 KB Output is correct
6 Correct 49 ms 5468 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 116 ms 7136 KB Output is correct
9 Correct 148 ms 8876 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 280 ms 11132 KB Output is correct
12 Correct 351 ms 13240 KB Output is correct
13 Incorrect 4 ms 2764 KB Output isn't correct