Submission #335999

#	Time	Username	Problem	Language	Result	Execution time	Memory
335999		Swan	Dreaming (IOI13_dreaming)	C++14	100 / 100	249 ms	22380 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define stop system("pause")

using namespace std;

const int maxn = 1e5+123;
vector<vector<pair<int, int> > > v;
vector<vector<pair<int, int> > > newGraph;
bool used[maxn];
pair<int, int> fst[maxn];
pair<int, int> snd[maxn];
int up[maxn];
vector<pair<int, int>> bestNodes;

void dfs(int u, int w, int p = -1){
    used[u] = 1;
    fst[u].first = 0;
    snd[u].first = 0;
    fst[u].second = -1;
    snd[u].second = -1;
    for(int i = 0; i < v[u].size();i++){
        int to = v[u][i].first;
        if(used[to])continue;
        dfs(to, v[u][i].second, u);
    }
    for(int i = 0; i < v[u].size();i++){
        int to = v[u][i].first;
        if(to == p)continue;
        if(fst[to].first + v[u][i].second > fst[u].first){
            snd[u] = fst[u];
            fst[u] = {fst[to].first + v[u][i].second, to};
        }else if(fst[to].first + v[u][i].second > snd[u].first){
            snd[u].first = fst[to].first + v[u][i].second;
            snd[u].second = to;
        }
        if(snd[to].first + v[u][i].second > snd[u].first && (fst[u].second != to)){
            snd[u].first = snd[to].first + v[u][i].second;
            snd[u].second = to;
        }
    }
}

void dfs2(int u, int w, int p = -1){
    used[u] = 1;
    if(p!= -1){
        up[u] = up[p] + w;
    }
    if(fst[p].second != u){
        up[u] = max(up[u], fst[p].first + w);
    }else{
        up[u] = max(up[u], snd[p].first + w);
    }
    for(int i = 0; i < v[u].size();i++){
        int to = v[u][i].first;
        if(used[to])continue;
        dfs2(to, v[u][i].second, u);
    }
}

pair<int,int> best;

void dfs3(int u){
    used[u] = 1;
    int kek = max(up[u], fst[u].first);
    if(kek < best.first){
        best.first = kek;
        best.second = u;
    }
    for(int i = 0; i < v[u].size();i++){
        int to = v[u][i].first;
        if(used[to])continue;
        dfs3(to);
    }
}

pair<int, int> findFarthest(int u, int p = -1){
    pair<int, int> best;
    best.first = 0;
    best.second = u;
    for(int i = 0; i < newGraph[u].size();i++){
        int to = newGraph[u][i].first;
        if(to == p)continue;
        int cost = newGraph[u][i].second;
        pair<int, int> b = findFarthest(to, u);
        if(cost + b.first > best.first){
            best = {cost + b.first, b.second};
        }
    }
    return best;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    v.resize(N + 2);
    newGraph.resize(N + 2);
    for(int i = 0; i < M;i++){
        int a = A[i];
        int b = B[i];
        v[a].push_back({b, T[i]});
        v[b].push_back({a, T[i]});
        newGraph[a].push_back({b, T[i]});
        newGraph[b].push_back({a, T[i]});
    }
    for(int i = 0; i < N;i++){
        if(!used[i])dfs(i, 0);
    }
    for(int i = 0; i < N;i++){
        used[i] = 0;
    }
    for(int i = 0; i < N;i++){
        if(!used[i])dfs2(i, 0);
    }
    for(int i = 0; i < N;i++){
        used[i] = 0;
    }
    for(int i = 0; i < N;i++){
        if(used[i])continue;
        best.first = INT_MAX;
        dfs3(i);
        bestNodes.push_back(best);
    }
    sort(bestNodes.begin(), bestNodes.end());
    for(int i = 0; i < bestNodes.size() - 1;i++){
        int from = bestNodes[i].second;
        int to = bestNodes.back().second;
        newGraph[from].push_back({to, L});
        newGraph[to].push_back({from, L});
        //cout << "ttt " << from << ' ' << to << ' ' << L << endl;
    }
    pair<int, int> fst = findFarthest(0);
    //cout << "da " << fst.second << endl;
    pair<int, int> snd = findFarthest(fst.second);
    return snd.first;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:22: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]
   22 |     for(int i = 0; i < v[u].size();i++){
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp:27: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]
   27 |     for(int i = 0; i < v[u].size();i++){
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, int)':
dreaming.cpp:54: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]
   54 |     for(int i = 0; i < v[u].size();i++){
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs3(int)':
dreaming.cpp:70: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]
   70 |     for(int i = 0; i < v[u].size();i++){
      |                    ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> findFarthest(int, int)':
dreaming.cpp:81: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]
   81 |     for(int i = 0; i < newGraph[u].size();i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:123: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]
  123 |     for(int i = 0; i < bestNodes.size() - 1;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