Submission #1302194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302194		damasen	Drivers (BOI24_drivers)	C++20	11 / 100	2087 ms	2064 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()
#define dbg(x) cerr << #x << " = " << x << '\n';

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]) continue;
        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;
    }
    while(m--){
        int x, y, w;
        cin >> x >> y >> w;
        edges.pb({w, x, y});
    }
    sort(all(edges));
    for(auto e : edges){
        unite(e[1], e[2], e[0]);
    }
    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);
    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: 0 / 10
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 23
• Subtask 5: 0 / 45