oj.uz

Submission #398993

# Submission time Handle Problem Language Result Execution time Memory
398993 2021-05-05T01:48:35 Z jlallas384 Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 11508 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    vector<vector<pair<int,int>>> g(n);
    for(int i = 0; i < m; i++){
        g[A[i]].emplace_back(B[i],T[i]);
        g[B[i]].emplace_back(A[i],T[i]);
    }
    vector<int> vis(n),mins;
    for(int i = 0; i < n; i++) if(!vis[i]){
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        vector<int> comp;
        while(q.size()){
            int v = q.front(); q.pop();
            comp.push_back(v);
            for(auto [u,w]: g[v]) if(!vis[u]){
                q.push(u);
                vis[u] = 1;
            }
        }
        int mn = 1e9;
        for(int st: comp){
            queue<tuple<int,int,int>> q;
            q.emplace(st,-1,0);
            int mx = 0;
            while(q.size()){
                auto [v,p,dst] = q.front(); q.pop();
                mx = max(mx,dst);
                for(auto [u,w]: g[v]) if(u != p){
                    q.emplace(u,v,w+dst);
                }
            }
            mn = min(mn,mx);
        }
        mins.push_back(mn);
    }
    sort(mins.rbegin(), mins.rend());
    assert(mins.size() == 2);
    int maxP = mins[0];
    int ans = maxP;
    for(int i = 1; i < mins.size(); i++){
        ans = max(ans,maxP + l + mins[i]);
    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:20:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |             for(auto [u,w]: g[v]) if(!vis[u]){
      |                      ^
dreaming.cpp:31:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |                 auto [v,p,dst] = q.front(); q.pop();
      |                      ^
dreaming.cpp:33:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |                 for(auto [u,w]: g[v]) if(u != p){
      |                          ^
dreaming.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 1; i < mins.size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 8556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 8556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 11508 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 8556 KB Time limit exceeded
2 Halted 0 ms 0 KB -