Submission #398993

#	Time	Username	Problem	Language	Result	Execution time	Memory
398993		jlallas384	Dreaming (IOI13_dreaming)	C++14	0 / 100	1090 ms	11508 KiB

dreaming

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23