oj.uz

Submission #430657

# Submission time Handle Problem Language Result Execution time Memory
430657 2021-06-16T18:04:16 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
18 / 100
 1000 ms 16212 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);
                                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 Execution timed out 1051 ms 16212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 Execution timed out 1051 ms 16212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7744 KB Output is correct
2 Correct 76 ms 7720 KB Output is correct
3 Correct 75 ms 7728 KB Output is correct
4 Correct 64 ms 7744 KB Output is correct
5 Correct 64 ms 7712 KB Output is correct
6 Correct 78 ms 8548 KB Output is correct
7 Correct 82 ms 7988 KB Output is correct
8 Correct 68 ms 7628 KB Output is correct
9 Correct 84 ms 7556 KB Output is correct
10 Correct 69 ms 7832 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 42 ms 8120 KB Output is correct
13 Correct 41 ms 8188 KB Output is correct
14 Correct 41 ms 8120 KB Output is correct
15 Correct 42 ms 8148 KB Output is correct
16 Correct 42 ms 8232 KB Output is correct
17 Correct 41 ms 8144 KB Output is correct
18 Correct 41 ms 8220 KB Output is correct
19 Correct 42 ms 8228 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 52 ms 8228 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 Execution timed out 1051 ms 16212 KB Time limit exceeded
2 Halted 0 ms 0 KB -