oj.uz

Submission #1111566

# Submission time Handle Problem Language Result Execution time Memory
1111566 2024-11-12T09:38:47 Z itslq Drivers (BOI24_drivers) C++17
10 / 100
 393 ms 81936 KB 
#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;

        if (T > P || root(A) != root(B)) {
            cout << "NE\n";
        } else {
            cout << "TAIP\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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80408 KB Output is correct
2 Correct 37 ms 80656 KB Output is correct
3 Correct 32 ms 80644 KB Output is correct
4 Correct 30 ms 80144 KB Output is correct
5 Correct 393 ms 81936 KB Output is correct

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 80152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80408 KB Output is correct
2 Correct 37 ms 80656 KB Output is correct
3 Correct 32 ms 80644 KB Output is correct
4 Correct 30 ms 80144 KB Output is correct
5 Correct 393 ms 81936 KB Output is correct
6 Incorrect 25 ms 80408 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80408 KB Output is correct
2 Correct 37 ms 80656 KB Output is correct
3 Correct 32 ms 80644 KB Output is correct
4 Correct 30 ms 80144 KB Output is correct
5 Correct 393 ms 81936 KB Output is correct
6 Incorrect 25 ms 80152 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 80408 KB Output is correct
2 Correct 37 ms 80656 KB Output is correct
3 Correct 32 ms 80644 KB Output is correct
4 Correct 30 ms 80144 KB Output is correct
5 Correct 393 ms 81936 KB Output is correct
6 Incorrect 25 ms 80152 KB Output isn't correct
7 Halted 0 ms 0 KB -