Submission #843597

#	Time	Username	Problem	Language	Result	Execution time	Memory
843597		anha3k25cvp	Dreaming (IOI13_dreaming)	C++14	18 / 100	45 ms	22868 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;

void dfs(int u) {
    vis[u] = 1;
    for (auto z : adj[u]) {
        int v = z.st, w = z.nd;
        if (vis[v])
            continue;
        dfs(v);
        f[u] = max(f[u], f[v] + w);
    }
}

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);
    vector <int> c;
    for (int i = 0; i < N; i ++)
        if (!vis[i]) {
            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 ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs_(int, int)':
dreaming.cpp:35: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]
   35 |     for (int i = 1; i < V.size(); i ++)
      |                     ~~^~~~~~~~~~
dreaming.cpp:39: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]
   39 |     for (int i = 0; i < V.size(); i ++) {
      |                     ~~^~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 1; i < c.size(); i ++) {
      |                     ~~^~~~~~~~~~
dreaming.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < c.size(); i ++) {
      |                     ~~^~~~~~~~~~

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