Submission #843608

#	Time	Username	Problem	Language	Result	Execution time	Memory
843608		anha3k25cvp	Dreaming (IOI13_dreaming)	C++14	0 / 100	52 ms	26704 KiB

dreaming

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "dreaming.h"

using namespace std;

const int inf = 7 + 1e9;

vector <int> vis, f, g;
vector <vector <II>> adj;
vector <vector <int>> a;

int dfs(int u) {
    int ans = 0;
    vis[u] = 1;
    for (auto z : adj[u]) {
        int v = z.st, w = z.nd;
        if (vis[v])
            continue;
        ans = max(ans, dfs(v));
        f[u] = max(f[u], f[v] + w);
        for (int i = 0; i < 2; i ++)
            if (a[v][i] + w > a[u][0]) {
                a[u][1] = a[u][0];
                a[u][0] = a[v][i] + w;
            }
            else if (a[v][i] + w > a[u][1])
                a[u][1] = a[v][i] + w;
    }
    return max(ans, a[u][0] + a[u][1]);
}

int dfs_(int u, int p) {
    int ans = max(f[u], g[u]);
    vector <II> V;
    for (auto z : adj[u])
        if (z.st != p)
            V.push_back(z);
    vector <int> l(V.size(), 0), r(V.size(), 0);
    for (int i = 1; i < V.size(); i ++)
        l[i] = max(l[i - 1], f[V[i - 1].st] + V[i - 1].nd);
    for (int i = (int)V.size() - 2; i >= 0; i --)
        r[i] = max(r[i + 1], f[V[i + 1].st] + V[i + 1].nd);
    for (int i = 0; i < V.size(); i ++) {
        int v = V[i].st, w = V[i].nd;
        g[v] = max({l[i], r[i], g[u]}) + w;
        ans = min(ans, dfs_(v, u));
    }
    return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.resize(N);
    for (int i = 0; i < M; i ++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    vis.assign(N, 0);
    f.assign(N, 0);
    g.assign(N, 0);
    a.assign(N, vector <int> (2, 0));
    vector <int> c;
    int ma = 0;
    for (int i = 0; i < N; i ++)
        if (!vis[i]) {
            ma = max(ma, dfs(i));
            int val = dfs_(i, 0);
            c.push_back(val);
        }
    if (c.size() == 1)
        return c[0];
    if (c.size() == 2)
        return c[0] + c[1] + L;
    vector <vector <int>> l(c.size(), vector <int> (2, 0)), r(c.size(), vector <int> (2, 0));
    for (int i = 1; i < c.size(); i ++) {
        l[i][0] = l[i - 1][0];
        l[i][1] = l[i - 1][1];
        if (c[i - 1] > l[i][0]) {
            l[i][1] = l[i][0];
            l[i][0] = c[i - 1];
        }
        else if (c[i - 1] > l[i][1])
            l[i][1] = c[i - 1];
    }
    for (int i = (int)c.size() - 2; i >= 0; i --) {
        r[i][0] = r[i + 1][0];
        r[i][1] = r[i + 1][1];
        if (c[i + 1] > r[i][0]) {
            r[i][1] = r[i][0];
            r[i][0] = c[i + 1];
        }
        else if (c[i + 1] > r[i][1])
            r[i][1] = c[i + 1];
    }
    int ans = inf;
    for (int i = 0; i < c.size(); i ++) {
        int ma1 = l[i][0], ma2 = l[i][1];
        for (int j = 0; j < 2; j ++)
            if (r[i][j] > ma1) {
                ma2 = ma1;
                ma1 = r[i][j];
            }
            else if (r[i][j] > ma2)
                ma2 = r[i][j];
        ans = min(ans, max(ma1 + c[i] + L, ma1 + ma2 + 2 * L));
    }
    return max(ans, ma);
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs_(int, int)':
dreaming.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i < V.size(); i ++)
      |                     ~~^~~~~~~~~~
dreaming.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < V.size(); i ++) {
      |                     ~~^~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 1; i < c.size(); i ++) {
      |                     ~~^~~~~~~~~~
dreaming.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i < c.size(); i ++) {
      |                     ~~^~~~~~~~~~

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