oj.uz

Submission #430664

# Submission time Handle Problem Language Result Execution time Memory
430664 2021-06-16T18:08:16 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
18 / 100
 265 ms 16680 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 - 4); j < min((int)pa.size(), (int)pa.size() / 2 + 4); 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 223 ms 16680 KB Output is correct
2 Correct 213 ms 16664 KB Output is correct
3 Correct 131 ms 11440 KB Output is correct
4 Correct 26 ms 4592 KB Output is correct
5 Correct 22 ms 3676 KB Output is correct
6 Correct 42 ms 5492 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 100 ms 7140 KB Output is correct
9 Correct 134 ms 8864 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 234 ms 11016 KB Output is correct
12 Correct 265 ms 13148 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 223 ms 16680 KB Output is correct
2 Correct 213 ms 16664 KB Output is correct
3 Correct 131 ms 11440 KB Output is correct
4 Correct 26 ms 4592 KB Output is correct
5 Correct 22 ms 3676 KB Output is correct
6 Correct 42 ms 5492 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 100 ms 7140 KB Output is correct
9 Correct 134 ms 8864 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 234 ms 11016 KB Output is correct
12 Correct 265 ms 13148 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 82 ms 7656 KB Output is correct
2 Correct 81 ms 7664 KB Output is correct
3 Correct 88 ms 7668 KB Output is correct
4 Correct 90 ms 7660 KB Output is correct
5 Correct 101 ms 7656 KB Output is correct
6 Correct 88 ms 8476 KB Output is correct
7 Correct 92 ms 7996 KB Output is correct
8 Correct 94 ms 7596 KB Output is correct
9 Correct 87 ms 7548 KB Output is correct
10 Correct 98 ms 7844 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 57 ms 8196 KB Output is correct
13 Correct 59 ms 8184 KB Output is correct
14 Correct 60 ms 8140 KB Output is correct
15 Correct 56 ms 8176 KB Output is correct
16 Correct 59 ms 8124 KB Output is correct
17 Correct 56 ms 8176 KB Output is correct
18 Correct 59 ms 8140 KB Output is correct
19 Correct 57 ms 8160 KB Output is correct
20 Correct 3 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 68 ms 8212 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 223 ms 16680 KB Output is correct
2 Correct 213 ms 16664 KB Output is correct
3 Correct 131 ms 11440 KB Output is correct
4 Correct 26 ms 4592 KB Output is correct
5 Correct 22 ms 3676 KB Output is correct
6 Correct 42 ms 5492 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 100 ms 7140 KB Output is correct
9 Correct 134 ms 8864 KB Output is correct
10 Correct 3 ms 2636 KB Output is correct
11 Correct 234 ms 11016 KB Output is correct
12 Correct 265 ms 13148 KB Output is correct
13 Incorrect 4 ms 2764 KB Output isn't correct