Submission #336140

#	Time	Username	Problem	Language	Result	Execution time	Memory
336140		aryan12	Dreaming (IOI13_dreaming)	C++17	100 / 100	272 ms	19308 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int N = 1e5 + 10;
vector<pair<int, int> > g[N];
bool vis[N];
int dist[N][2];
int idx, maxdist;
pair<int, int> diameter;
set<int> comp;

void Initialize() {
    diameter.first = 0;
    diameter.second = 0;
    for(int i = 0; i < N; i++) {
        g[i].clear();
        vis[i] = false;
        dist[i][0] = 0;
        dist[i][1] = 0;
    }
}

void dfs(int node, int par, int wt, int state) {
    vis[node] = true;
    comp.insert(node);
    if(maxdist < wt) {
        maxdist = wt;
        idx = node;
    }
    dist[node][state] = wt;
    for(int i = 0; i < g[node].size(); i++) {
        if(g[node][i].first == par)
            continue;
        dfs(g[node][i].first, node, wt + g[node][i].second, state);
    }
}

int travelTime(int n, int m, int l, int v[], int u[], int w[]) {
    Initialize();
    for(int i = 0; i < m; i++) {
        g[u[i]].push_back({v[i], w[i]});
        g[v[i]].push_back({u[i], w[i]});
    }
    int ans = 0;
    vector<int> temp;
    for(int i = 0; i < n; i++) {
        if(!vis[i]) {
            idx = 0;
            maxdist = -1;
            dfs(i, -1, 0, 0);
            diameter.first = idx;
            maxdist = -1;
            dfs(idx, -1, 0, 0);
            diameter.second = idx;
            ans = max(ans, maxdist);
            //cout << "i = " << i << ", diameter nodes = " << diameter.first << ", " << diameter.second << ", maxdist = " << maxdist << endl;
            int best = maxdist;
            maxdist = -1;
            dfs(idx, -1, 0, 1);
            for(auto i: comp) {
                best = min(best, max(dist[i][0], dist[i][1]));
            }
            comp.clear();
            temp.push_back(best);
        }
    }
    sort(temp.begin(), temp.end());
    reverse(temp.begin(), temp.end());
    if(n - m >= 2) {
        ans = max(ans, temp[0] + temp[1] + l);
    }
    if(n - m >= 3) {
        ans = max(ans, temp[1] + temp[2] + 2 * l);
    }
    return ans;
}

/*int main() {
    int n, m, l;
    cin >> n >> m >> l;
    int a[m], b[m], c[m];
    for(int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    cout << travelTime(n, m, l, a, b, c) << endl;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int, int)':
dreaming.cpp:32: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]
   32 |     for(int i = 0; i < g[node].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