제출 #1111555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111555		itslq	Drivers (BOI24_drivers)	C++17	11 / 100	2101 ms	81680 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX = 200005, LOG = 21;

vector<int> depth(MAX, 0), ufdspa(MAX), ufdsrk(MAX);
vector<vector<pair<int, int>>> twok(LOG, vector<pair<int, int>>(MAX, make_pair(-1, INT_MAX)));
vector<vector<pair<int, int>>> adjList(MAX), MSTList(MAX);

int root(int n) {
    if (ufdspa[n] == n) return n;
    return ufdspa[n] = root(ufdspa[n]);
}

void merge(int a, int b) {
    int x = root(a), y = root(b);
    if (x == y) return;
    if (ufdsrk[x] > ufdsrk[y]) ufdspa[y] = x;
    else if (ufdsrk[x] < ufdsrk[y]) ufdspa[x] = y;
    else {
        ufdspa[x] = y;
        ufdsrk[y]++;
    }
}

void rec(int n, int p = -1) {
    for (pair<int, int> adj: MSTList[n]) {
        if (adj.second == p) continue;
        //cout << adj.first << "***\n";
        twok[0][adj.second] = make_pair(n, adj.first);
        depth[adj.second] = depth[n] + 1;
        rec(adj.second, n);
    }
}

pair<int, int> kpar(int x, int k){
    //cout << x << '-' << k << endl;
    int L = 0;
	for (int j = 0; j < LOG; j++){
		if (x == -1) break;
		if (k & (1 << j)) {
            L = max(L, twok[j][x].second);
            x = twok[j][x].first;
		}
	}
	//cout << "kpar returns " << x << " " << L << endl;
	return make_pair(x, L);
}

int ans(int a, int b) {
    if (root(a) != root(b)) return INT_MAX;
    if (depth[a] < depth[b]) swap(a, b);

    pair<int, int> p = kpar(a, depth[a] - depth[b]);
    //cout << depth[a] - depth[b] << "th ";
    a = p.first;
    //cout << "PARENT IS: " << a << '\n';
    int L = p.second;

    if (a == b) return L;

    for (int k = LOG - 1; k >= 0; k--){
        if (twok[k][a].first != twok[k][b].first){
            L = max(L, max(twok[k][a].second, twok[k][b].second));
            a = twok[k][a].first; b = twok[k][b].first;
        }
    }

    return max(L, max(twok[0][a].second, twok[0][b].second));
}

signed main() {
    int N, M, U, X, Y, T, A, B, P;
    pair<int, pair<int, int>> curr;
    cin >> N >> M >> U;
    vector<bool> vis(N);
    for (int i = 0; i < M; i++) {
        cin >> X >> Y >> T;
        --X; --Y;
        adjList[X].emplace_back(T, Y);
        adjList[Y].emplace_back(T, X);
    }
    for (int i = 0; i < N; i++) ufdspa[i] = i;

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    for (int k = 0; k < N; k++) {
        if (vis[k]) continue;

        pq = priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>>();
        pq.emplace(0, make_pair(k, k));
        while (!pq.empty()) {
            curr = pq.top();
            pq.pop();

            if (vis[curr.second.second]) continue;
            vis[curr.second.second] = 1;

            if (curr.second.first != k || curr.second.second != k) {
                MSTList[curr.second.first].emplace_back(curr.first, curr.second.second);
                MSTList[curr.second.second].emplace_back(curr.first, curr.second.first);
                merge(curr.second.first, curr.second.second);
            }

            for (pair<int, int> adj: adjList[curr.second.second]) {
                if (vis[adj.second]) continue;
                pq.emplace(adj.first, make_pair(curr.second.second, adj.second));
            }
        }

        rec(k);
    }

    while (U--) {
        cin >> A >> B >> P;
        --A; --B;
        vector<bool> v(N);
        queue<int> q;

        q.push(A);
        v[A] = 1;
        bool f = 0;
        while (!q.empty()) {
            if (q.front() == B) {
                cout << "TAIP\n";
                f = 1;
                break;
            }
            for (pair<int, int> adj: MSTList[q.front()]) {
                if (v[adj.second] || adj.first > P) continue;
                q.push(adj.second);
                v[adj.second] = 1;
            }
            q.pop();
        }

        if (!f) cout << "NE\n";

        //cout << (ans(--A, --B)) << endl;
        //cout << (ans(--A, --B) > P ? "NE" : "TAIP") << endl;
    }
    //for (int i = 0; i < N; i++) cout << pa[i] << " ";
}
/*
8 7 10
1 2 3
1 3 5
1 4 4
3 5 2
4 5 3
6 8 4
6 7 1*/

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