Submission #1302204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302204		damasen	Drivers (BOI24_drivers)	C++20	55 / 100	2096 ms	28400 KiB

Main

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

#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) (int)x.size()

const int INF = 1e18;

vector<int> parent, sizes;
vector<array<int, 3>> edges, good;

int find(int u){
    if(parent[u] == u) return u;
    return parent[u] = find(parent[u]);
}

void unite(int v, int u, int w){
    v = find(v);
    u = find(u);
    if(v != u){
        if(sizes[u] < sizes[v]) swap(u, v);
        parent[v] = u;
        sizes[u] += sizes[v];
        good.pb({v, u, w});
    }
}

vector<vector<pair<int, int>>> adj;
vector<int> vis;
int the;

void dfs(int node, int b, int cur){
    if(vis[node] || the != -1) return;
    vis[node] = 1;
    if(node == b){
        the = cur;
        return;
    }
    for(auto go : adj[node]){
        if(!vis[go.first])
            dfs(go.first, b, max(cur, go.second));
    }
}

void solve(){
    int n, m, u;
    cin >> n >> m >> u;

    edges.clear();
    good.clear();

    parent.resize(n + 1);
    sizes.assign(n + 1, 1);
    for(int i = 0; i <= n; i++) parent[i] = i;

    // read edges
    while(m--){
        int x, y, w;
        cin >> x >> y >> w;
        edges.pb({w, x, y});
    }

    // sort edges by weight
    sort(all(edges));

    // check subtask 1 condition (all weights equal)
    bool same = true;
    for(int i = 1; i < sz(edges); i++){
        if(edges[i][0] != edges[0][0]){
            same = false;
            break;
        }
    }

    // build DSU / MST
    for(auto e : edges){
        unite(e[1], e[2], e[0]);
    }

    // subtask 1 solution
    if(same){
        while(u--){
            int a, b, t;
            cin >> a >> b >> t;
            if(find(a) == find(b) && edges[0][0] <= t)
                cout << "TAIP\n";
            else
                cout << "NE\n";
        }
        return;
    }

    // build MST adjacency list
    adj.assign(n + 1, {});
    for(auto e : good){
        adj[e[0]].pb({e[1], e[2]});
        adj[e[1]].pb({e[0], e[2]});
    }

    vis.assign(n + 1, 0);

    // general (slow) solution
    while(u--){
        int a, b, t;
        cin >> a >> b >> t;
        fill(vis.begin(), vis.end(), 0);
        the = -1;
        dfs(a, b, 0);
        if(the == -1 || the > t) cout << "NE\n";
        else cout << "TAIP\n";
    }
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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