Submission #293203

#	Time	Username	Problem	Language	Result	Execution time	Memory
293203		alexandra_udristoiu	Dreaming (IOI13_dreaming)	C++14	100 / 100	136 ms	14832 KiB

dreaming

#include "dreaming.h"
#include<algorithm>
#include<vector>
#define DIM 100005
#define f first
#define s second
using namespace std;
static int viz[DIM], w[DIM], df[DIM], d[DIM][2], nr;
static vector< pair<int, int> > v[DIM];
static void dfs1(int nod){
    viz[nod] = 1;
    d[nod][0] = d[nod][1] = 0;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i].f;
        if(viz[vecin] == 0){
            dfs1(vecin);
            if(d[vecin][0] + v[nod][i].s > d[nod][0]){
                d[nod][1] = d[nod][0];
                d[nod][0] = d[vecin][0] + v[nod][i].s;
            }
            else{
                d[nod][1] = max(d[nod][1], d[vecin][0] + v[nod][i].s);
            }
        }
    }
}
static void dfs2(int nod){
    viz[nod] = 2;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i].f;
        if(viz[vecin] == 1){
            df[vecin] = df[nod] + v[nod][i].s;
            if(d[nod][0] != d[vecin][0] + v[nod][i].s){
                df[vecin] = max(df[vecin], d[nod][0] + v[nod][i].s);
            }
            else{
                df[vecin] = max(df[vecin], d[nod][1] + v[nod][i].s);
            }
            w[nr] = min(w[nr], max(d[vecin][0], df[vecin]) );
            dfs2(vecin);
        }
    }
}

int travelTime(int n, int m, int k, int a[], int b[], int t[]) {
    int i, sol;
    for(i = 0; i < m; i++){
        v[ a[i] ].push_back( make_pair(b[i], t[i]) );
        v[ b[i] ].push_back( make_pair(a[i], t[i]) );
    }
    for(i = 0; i < n; i++){
        if(viz[i] == 0){
            dfs1(i);
        }
    }
    for(i = 0; i < n; i++){
        if(viz[i] == 1){
            nr++;
            w[nr] = d[i][0];
            dfs2(i);
        }
    }
    sort(w + 1, w + nr + 1);
    if(nr == 2){
        sol = w[nr] + w[nr - 1] + k;
    }
    else{
        sol = max(w[nr] + w[nr - 1] + k, w[nr - 1] + w[nr - 2] + 2 * k);
    }
    if(nr == 1){
        sol = w[1];
    }
    for(i = 0; i < n; i++){
        sol = max(sol, d[i][0] + d[i][1]);
    }
    return sol;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23