oj.uz

Submission #97574

# Submission time Handle Problem Language Result Execution time Memory
97574 2019-02-17T08:29:16 Z georgerapeanu Dreaming (IOI13_dreaming) C++11
0 / 100
 61 ms 15224 KB 
#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int NMAX = 1e5;

pair<int,int> link[NMAX + 5];

vector< pair<int,int> > graph[NMAX + 5];

bool viz[NMAX + 5];

struct data_t{
    int best_dist;
    int node;
};


data_t dfs(int nod,int tata){
    viz[nod] = true;
    data_t ans;
    ans.node = nod;
    ans.best_dist = 0;

    link[nod] = {-1,-1};

    for(auto it:graph[nod]){
        if(it.first == tata){
            continue;
        }
        data_t tmp = dfs(it.first,nod);
        if(ans.best_dist <= tmp.best_dist + it.second){
            ans.best_dist = tmp.best_dist + it.second;
            ans.node = tmp.node;
            link[nod] = it;
        }
    }

    return ans;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int ans = 0;

    for(int i = 0;i < M;i++){
        graph[A[i]].push_back({B[i],T[i]});
        graph[B[i]].push_back({A[i],T[i]});
    }

    vector<int> d;

    for(int i = 0;i < N;i++){
        if(viz[i]){
            continue;
        }

        data_t tmp = dfs(i,0);
        data_t aux = dfs(tmp.node,0);

        vector<int> diam;
        int len = 0;
        diam.push_back(0);
        for(int node = tmp.node;link[node].first != -1;node = link[node].first){
            diam.push_back(link[node].second);
            len += diam.back();
        }

        ans = max(ans,len);

        int best = 1 << 30;
        int pref = 0;

        for(int i = 0;i < (int)diam.size();i++){
            pref += diam[i];
            best = min(best,max(pref,len - pref));
        }
        
        d.push_back(best);
    }

    sort(d.begin(),d.end());
    reverse(d.begin(),d.end());

    return max(max(ans,d[0] + d[1] + L),d[1] + L + d[2] + L);
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:16: warning: variable 'aux' set but not used [-Wunused-but-set-variable]
         data_t aux = dfs(tmp.node,0);
                ^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15224 KB Output is correct
2 Correct 60 ms 15224 KB Output is correct
3 Correct 46 ms 10872 KB Output is correct
4 Correct 11 ms 4528 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 16 ms 5504 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15224 KB Output is correct
2 Correct 60 ms 15224 KB Output is correct
3 Correct 46 ms 10872 KB Output is correct
4 Correct 11 ms 4528 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 16 ms 5504 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15224 KB Output is correct
2 Correct 60 ms 15224 KB Output is correct
3 Correct 46 ms 10872 KB Output is correct
4 Correct 11 ms 4528 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 16 ms 5504 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 6236 KB Output is correct
2 Correct 44 ms 6316 KB Output is correct
3 Correct 34 ms 6144 KB Output is correct
4 Correct 34 ms 6144 KB Output is correct
5 Correct 35 ms 6272 KB Output is correct
6 Correct 33 ms 6648 KB Output is correct
7 Correct 33 ms 6400 KB Output is correct
8 Correct 41 ms 6136 KB Output is correct
9 Correct 30 ms 6140 KB Output is correct
10 Correct 31 ms 6264 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 11 ms 4220 KB Output is correct
13 Correct 11 ms 4220 KB Output is correct
14 Correct 12 ms 4220 KB Output is correct
15 Correct 11 ms 4220 KB Output is correct
16 Correct 12 ms 4220 KB Output is correct
17 Correct 11 ms 4088 KB Output is correct
18 Correct 11 ms 4220 KB Output is correct
19 Correct 11 ms 4092 KB Output is correct
20 Incorrect 3 ms 2688 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15224 KB Output is correct
2 Correct 60 ms 15224 KB Output is correct
3 Correct 46 ms 10872 KB Output is correct
4 Correct 11 ms 4528 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 16 ms 5504 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15224 KB Output is correct
2 Correct 60 ms 15224 KB Output is correct
3 Correct 46 ms 10872 KB Output is correct
4 Correct 11 ms 4528 KB Output is correct
5 Correct 13 ms 3584 KB Output is correct
6 Correct 16 ms 5504 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Halted 0 ms 0 KB -