oj.uz

Submission #1076001

# Submission time Handle Problem Language Result Execution time Memory
1076001 2024-08-26T10:22:23 Z TheQuantiX Dreaming (IOI13_dreaming) C++17
18 / 100
 44 ms 20816 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;
    mx[x] = 0;
    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:133:23: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
  133 |     if (vp.size() + m != n) {
      |         ~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 44 ms 20816 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 22 ms 9184 KB Output is correct
2 Correct 28 ms 9180 KB Output is correct
3 Correct 22 ms 9184 KB Output is correct
4 Correct 25 ms 9180 KB Output is correct
5 Correct 21 ms 9180 KB Output is correct
6 Correct 22 ms 9940 KB Output is correct
7 Correct 24 ms 9692 KB Output is correct
8 Correct 20 ms 8928 KB Output is correct
9 Correct 27 ms 8916 KB Output is correct
10 Correct 22 ms 9428 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 10 ms 6820 KB Output is correct
13 Correct 9 ms 6868 KB Output is correct
14 Correct 9 ms 6868 KB Output is correct
15 Correct 10 ms 6868 KB Output is correct
16 Correct 10 ms 6612 KB Output is correct
17 Correct 10 ms 6244 KB Output is correct
18 Correct 9 ms 7124 KB Output is correct
19 Correct 9 ms 6612 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 2788 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 9 ms 6612 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 44 ms 20816 KB Output isn't correct
2 Halted 0 ms 0 KB -