Submission #679324

#	Time	Username	Problem	Language	Result	Execution time	Memory
679324		kusssso	꿈 (IOI13_dreaming)	C++17	100 / 100	89 ms	15996 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
#define fi first
#define se second

vector<int> Tree;
int d[N];
bool used[N];
int pa[N];

vector<pair<int, int>> g[N];

void dfs (int u, int p = -1) {
    Tree.push_back(u);
    used[u] = 1;
    pa[u] = p;
    for (auto& e : g[u]) {
        int v = e.fi;
        int w = e.se;
        if (v != p) {
            d[v] = d[u] + w;
            dfs(v, u);
        }
    }
}

// int travelTime (int n, int m, int L, vector<int> A, vector<int> B, vector<int> T) {
    
int travelTime (int n, int m, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < m; i++) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    int longest = 0;
    int mxrad = -1;
    int root = 0;
    vector<int> center;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
            int v = i;
            for (auto& j : Tree) if (d[j] > d[v]) v = j;
            Tree.clear();
            d[v] = 0;
            dfs(v);
            for (auto &j : Tree) if (d[j] > d[v]) v = j;
            int u = v;
            int x = v;
            while (u != -1) {
                if (max(d[u], d[v] - d[u]) < max(d[x], d[v] - d[x])) x = u;
                u = pa[u];
            }
            if (mxrad < max(d[x], d[v] - d[x])) {
                mxrad = max(d[x], d[v] - d[x]);
                root = x;
            }
            center.push_back(x);
            longest = max(longest, d[v]);
            Tree.clear();
        }
    }
    for (int i = 0; i < center.size(); i++) {
        if (center[i] != root) {
            g[root].push_back({center[i], L});
            g[center[i]].push_back({root, L});
        }
    }
    dfs(0);
    int v = 0;
    assert(Tree.size() == n);
    for (auto &j : Tree) if (d[j] > d[v]) v = j;
    Tree.clear();
    d[v] = 0;
    dfs(v);
    for (auto &j : Tree) if (d[j] > d[v]) v = j;
    longest = max(longest, d[v]);

    return longest;
}

// signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
//     
    // int n, m, L;
    // cin >> n >> m >> L;
    // vector<int> A(m), B(m), T(m);
    // for (int i = 0; i < m; i++) cin >> A[i] >> B[i] >> T[i];
//     
    // cout << travelTime(n,m,L,A,B,T);
//     
    // return 0;
// }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < center.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dreaming.cpp:1:
dreaming.cpp:73:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     assert(Tree.size() == n);
      |            ~~~~~~~~~~~~^~~~

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