oj.uz

Submission #430661

# Submission time Handle Problem Language Result Execution time Memory
430661 2021-06-16T18:07:21 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
18 / 100
 731 ms 16304 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 - 3); j < min((int)pa.size(), (int)pa.size() / 2 + 3); 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 705 ms 16304 KB Output is correct
2 Correct 731 ms 16212 KB Output is correct
3 Correct 385 ms 11504 KB Output is correct
4 Correct 65 ms 4556 KB Output is correct
5 Correct 45 ms 3660 KB Output is correct
6 Correct 105 ms 5572 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 229 ms 7128 KB Output is correct
9 Correct 326 ms 9172 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 489 ms 10948 KB Output is correct
12 Correct 616 ms 13504 KB Output is correct
13 Incorrect 5 ms 2764 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 3 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 705 ms 16304 KB Output is correct
2 Correct 731 ms 16212 KB Output is correct
3 Correct 385 ms 11504 KB Output is correct
4 Correct 65 ms 4556 KB Output is correct
5 Correct 45 ms 3660 KB Output is correct
6 Correct 105 ms 5572 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 229 ms 7128 KB Output is correct
9 Correct 326 ms 9172 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 489 ms 10948 KB Output is correct
12 Correct 616 ms 13504 KB Output is correct
13 Incorrect 5 ms 2764 KB Output isn't correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7856 KB Output is correct
2 Correct 78 ms 7752 KB Output is correct
3 Correct 72 ms 7664 KB Output is correct
4 Correct 68 ms 7652 KB Output is correct
5 Correct 72 ms 7856 KB Output is correct
6 Correct 66 ms 8424 KB Output is correct
7 Correct 86 ms 8088 KB Output is correct
8 Correct 74 ms 7576 KB Output is correct
9 Correct 61 ms 7616 KB Output is correct
10 Correct 67 ms 7884 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 43 ms 8196 KB Output is correct
13 Correct 41 ms 8156 KB Output is correct
14 Correct 41 ms 8132 KB Output is correct
15 Correct 41 ms 8120 KB Output is correct
16 Correct 41 ms 8168 KB Output is correct
17 Correct 43 ms 8152 KB Output is correct
18 Correct 44 ms 8148 KB Output is correct
19 Correct 45 ms 8120 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 41 ms 8208 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 3 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 705 ms 16304 KB Output is correct
2 Correct 731 ms 16212 KB Output is correct
3 Correct 385 ms 11504 KB Output is correct
4 Correct 65 ms 4556 KB Output is correct
5 Correct 45 ms 3660 KB Output is correct
6 Correct 105 ms 5572 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 229 ms 7128 KB Output is correct
9 Correct 326 ms 9172 KB Output is correct
10 Correct 4 ms 2636 KB Output is correct
11 Correct 489 ms 10948 KB Output is correct
12 Correct 616 ms 13504 KB Output is correct
13 Incorrect 5 ms 2764 KB Output isn't correct