제출 #1163855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163855		PakinDioxide	Drivers (BOI24_drivers)	C++17	55 / 100	2097 ms	43960 KiB

Main

#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector <pair <int, int>> adj[200005], Adj[200005];
pair <int, int> up[200005];
int dep[200005], vis[200005], V[200005], par[200005];
map <pair <int, int>, int> dp;

void dfs(int u, int p) {
    vis[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == p) continue;
        up[v] = {u, w};
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Adj[u].emplace_back(v, w), Adj[v].emplace_back(u, w);
    }
    priority_queue <tuple <int, int, int>> Q;
    for (int i = 1; i <= n; i++) {
        if (V[i]) continue;
        Q.emplace(INT_MIN, i, i);
        while (!Q.empty()) {
            auto [w, u, p] = Q.top(); w = -w;
            Q.pop();
            if (V[u]) continue;
            V[u] = 1;
            par[u] = i;
            if (w > INT_MIN) adj[u].emplace_back(p, w);
            if (w > INT_MIN) adj[p].emplace_back(u, w);
            for (auto [v, ww] : Adj[u]) {
                if (V[v]) continue;
                Q.emplace(-ww, v, u);
            }
        }
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, 0);
    function <int(int)> fi = [&] (int x) {return par[x];};
    while (q--) {
        int u, v, p, uu, vv;
        cin >> u >> v >> p;
        if (dp[{u, v}] == 1) {cout << "TAIP\n"; continue;}
        else if (dp[{u, v}] == 2) {cout << "NE\n"; continue;}
        if (fi(u) != fi(v)) {dp[{u, v}] = 2; cout << "NE\n"; continue;}
        uu = u, vv = v;
        int mx = INT_MIN;
        if (dep[v] > dep[u]) swap(u, v);
        while (dep[u] > dep[v]) {if (mx > p) break; mx = max(mx, up[u].second), u = up[u].first;}
        while (u != v) {if (mx > p) break; mx = max({mx, up[u].second, up[v].second}), u = up[u].first, v = up[v].first;}
        if (mx > p) dp[{uu, vv}] = 2, cout << "NE\n";
        else dp[{uu, vv}] = 1, cout << "TAIP\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 0 / 45