Submission #1111498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111498		itslq	Drivers (BOI24_drivers)	C++17	0 / 100	29 ms	80656 KiB

Main

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

#define int long long

const int MAX = 200005, LOG = 21;

vector<int> depth(MAX, 0);
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);

vector<int> ufdspa(200005), ufdsrk(200005);

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;
        }
    }
    if (twok[LOG - 1][a].first != twok[LOG - 1][b].first) return INT_MAX;

    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);
    }

    for (int i = 0; i < N; i++) {
        for (int j = 1; j < 20; j++) {
            if (twok[j - 1][i].first == -1) break;
            twok[j][i].first = twok[j - 1][twok[j - 1][i].first].first;
            twok[j][i].second = max(twok[j - 1][i].second, twok[j - 1][twok[j - 1][i].first].second);
        }
    }

    /*for (int i = 0 ; i < N; i++) {
        cout << "(" << i << "): ";
        for (int j = 0; j < LOG; j++) cout << twok[j][i].first << " [" << twok[j][i].second << "] ";
        cout << endl;
    }*/

    //for (int i = 0; i < N; i++) cout << depth[i] << " " << endl;

    while (U--) {
        cin >> A >> B >> P;
        //cout << (ans(--A, --B)) << endl;
        cout << (ans(--A, --B) > P ? "NE" : "TAIP") << endl;
    }
    //for (int i = 0; i < N; i++) cout << pa[i] << " ";
}

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