Submission #745857

#	Time	Username	Problem	Language	Result	Execution time	Memory
745857		chanhchuong123	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	530 ms	62192 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1 << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};

const int INF = 2e9 + 7;
const int MAX = 100100;
int n, m, k;
bool exist[MAX];
vector<pair<int, int>> adj[MAX];

namespace subtask1 {
    int dp[MAX];

    void dfs(int u, int p) {
        if (u && adj[u].size() == 1) {
            if (exist[u]) dp[u] = 0;
            return;
        }

        vector<long long> arr;
        for (pair<int, int> &x: adj[u]) if (x.fi != p) {
            int v = x.fi, w = x.se; dfs(v, u);
            if (dp[v] != INF) arr.push_back(w + dp[v]);
        }

        if (arr.size() > 1) {
            sort(all(arr));
            dp[u] = arr[1];
        }
    }

    int solve(void) {
        for (int i = 0; i < n; ++i) dp[i] = INF; dfs(0, -1);
        return (dp[0] == INF ? -1 : dp[0]);
    }
}

namespace fullsubtask {
    struct node {
        int u, t, dist;

        node(int _u = 0, int _t = 0, int _dist = 0) {
            u = _u; t = _t; dist = _dist;
        }

        bool operator< (const node &other) const {
            return dist > other.dist;
        }
    };
    priority_queue<node> pq;

    int d[MAX][2];

    int solve(void) {
        for (int i = 0; i < n; ++i) d[i][0] = d[i][1] = INF;
        for (int i = 0; i < n; ++i) if (exist[i]) {
            pq.push(node(i, 1, 0));
            d[i][0] = 0;
            d[i][1] = 0;
        }
        while (pq.size()) {
            int u = pq.top().u;
            int t = pq.top().t;
            int dist = pq.top().dist;
            pq.pop();
            if (t == 0) continue;
            if (dist != d[u][t]) continue;

            for (pair<int, int> &x: adj[u]) {
                int v = x.fi, w = x.se;
                for (int i = 0; i < 2; ++i) if (d[v][i] >= dist + w) {
                    for (int j = 1; j > i; --j) {
                        if (minimize(d[v][j], d[v][j - 1]) && j)
                            pq.push(node(v, j, d[v][j]));
                    }
                    if (minimize(d[v][i], dist + w) && i)
                        pq.push(node(v, i, d[v][i]));
                    break;
                }
            }
        }
        return (d[0][1] == INF ? -1 : d[0][1]);
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N; m = M; k = K;
    for (int i = 0; i < m; ++i) {
        adj[R[i][0]].push_back({R[i][1], L[i]});
        adj[R[i][1]].push_back({R[i][0], L[i]});
    }
    for (int i = 0; i < k; ++i) {
        exist[P[i]] = true;
    }
    if (m == n - 1) return subtask1::solve();
    return fullsubtask::solve();
}

Compilation message (stderr)

crocodile.cpp: In function 'int subtask1::solve()':
crocodile.cpp:51:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |         for (int i = 0; i < n; ++i) dp[i] = INF; dfs(0, -1);
      |         ^~~
crocodile.cpp:51:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |         for (int i = 0; i < n; ++i) dp[i] = INF; dfs(0, -1);
      |                                                  ^~~

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11