oj.uz

Submission #1075995

# Submission time Handle Problem Language Result Execution time Memory
1075995 2024-08-26T10:20:36 Z TheQuantiX Dreaming (IOI13_dreaming) C++17
18 / 100
 46 ms 19536 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000LL;

ll n, m, q, k, x, y, a, b, c;
int l;
vector< pair<ll, ll> > G[100000];
ll mx[100000], mxu[100000];
bool vis[100000];

struct dsu {
    ll n;
    vector<ll> par;
    vector<ll> sz;

    dsu(ll N) : n(N) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    ll find_p(ll x) {
        if (x == par[x]) {
            return x;
        }
        ll p = find_p(par[x]);
        par[x] = p;
        return p;
    }

    void join(ll x, ll y) {
        x = find_p(x);
        y = find_p(y);
        if (x == y) {
            return;
        }
        if (sz[y] > sz[x]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};

void dfs(ll x, ll p) {
    vis[x] = 1;
    for (auto i : G[x]) {
        if (i.first != p) {
            dfs(i.first, x);
            mx[x] = max(mx[x], mx[i.first] + i.second);
        }
    }
}

void dfsu(ll x, ll p) {
    vector< pair<ll, ll> > v;
    for (auto i : G[x]) {
        if (i.first != p) {
            v.push_back({mx[i.first] + i.second, i.first});
        }
    }
    sort(v.rbegin(), v.rend());
    for (auto i : G[x]) {
        if (i.first != p) {
            mxu[i.first] = mxu[x] + i.second;
            if (v.size() > 1) {
                if (v[0].second != i.first) {
                    mxu[i.first] = max(mxu[i.first], v[0].first + i.second);
                }
                else {
                    mxu[i.first] = max(mxu[i.first], v[1].first + i.second);
                }
            }
            dfsu(i.first, x);
        }
    }
    // cout << x << ' ' << mx[x] << ' ' << mxu[x] << '\n';
}

pair<ll, ll> dfsp(ll x, ll p) {
    pair<ll, ll> pr = {max(mx[x], mxu[x]), x};
    for (auto i : G[x]) {
        if (i.first != p) {
            pr = min(pr, dfsp(i.first, x));
        }
    }
    return pr;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    l = L;
    dsu d(n);
    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]});
        d.join(A[i], B[i]);
    }
    vector< pair<int, int> > vp;
    if (n <= 3000) {
        vector< pair<ll, ll> > vec(n, {INF, INF});
        for (ll i = 0; i < n; i++) {
            dfs(i, -1);
            vec[d.find_p(i)] = min(vec[d.find_p(i)], make_pair(mx[i], i));
        }
        for (ll i = 0; i < n; i++) {
            if (d.par[i] == i) {
                vp.push_back(vec[i]);
            }
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                dfs(i, -1);
                dfsu(i, -1);
                vp.push_back(dfsp(i, -1));
            }
        }
    }
    // for (auto i : vp) {
    //     cout << i.first << ' ' << i.second << '\n';
    // }
    if (vp.size() + m != n) {
        exit(-1);
    }
    sort(vp.rbegin(), vp.rend());
    int ans = vp[0].first;
    if (vp.size() > 1) {
        ans = max(ans, vp[0].first + vp[1].first + l);
    }
    if (vp.size() > 2) {
        ans = max(ans, vp[1].first + vp[2].first + l * 2);
    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:132:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
  132 |     if (vp.size() + m != n) {
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 19536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 19536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8668 KB Output is correct
2 Correct 23 ms 9176 KB Output is correct
3 Correct 26 ms 9104 KB Output is correct
4 Correct 38 ms 9176 KB Output is correct
5 Correct 22 ms 9176 KB Output is correct
6 Correct 23 ms 9948 KB Output is correct
7 Correct 21 ms 9436 KB Output is correct
8 Correct 21 ms 8924 KB Output is correct
9 Correct 20 ms 8916 KB Output is correct
10 Correct 23 ms 9172 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 11 ms 6356 KB Output is correct
13 Correct 9 ms 6608 KB Output is correct
14 Correct 10 ms 6484 KB Output is correct
15 Correct 12 ms 6612 KB Output is correct
16 Correct 9 ms 6236 KB Output is correct
17 Correct 10 ms 5844 KB Output is correct
18 Correct 9 ms 6612 KB Output is correct
19 Correct 10 ms 6608 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 2 ms 2680 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 9 ms 6352 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 19536 KB Output isn't correct
2 Halted 0 ms 0 KB -