제출 #1232279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232279		ThommyDB	Drivers (BOI24_drivers)	C++20	100 / 100	338 ms	21552 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long

const int INF = 1e16;

int n, m, u;
vector<pair<int, pair<int, int>>> edges;
vector<int> p, siz;

int find(int x){
    int xx = x;
    while(p[x]!=x) x=p[x];
    p[xx]=x;
    return x;
}

void unite(int a, int b){
    a=find(a);
    b=find(b);
    if(siz[a]>siz[b])swap(a, b);
    siz[a]+=siz[b];
    p[b]=a;
}

bool same(int a, int b){
    return find(a)==find(b);
}

signed main(){
    cin >> n >> m >> u;
    edges.resize(m);
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    siz.resize(n, 1);
    for(int i = 0; i < m; i++){
        int a, b, t;
        cin >> a >> b >> t; a--; b--;
        edges[i]={t, {a, b}};
    }
    sort(edges.begin(), edges.end());
    edges.push_back({INF, {-1, -1}});

    vector<pair<pair<int, int>, pair<int, int>>> queries(u);
    for(int i = 0; i < u; i++){
        int p, a, b;
        cin >> a >> b >> p; a--; b--;
        queries[i]={{p, i}, {a, b}};
    }
    sort(queries.begin(), queries.end());

    vector<string> ans(u);

    int road = 0;
    for(int i = 0; i < u; i++){
        int p = queries[i].first.first, a=queries[i].second.first, b=queries[i].second.second;
        while(edges[road].first <= p){
            unite(edges[road].second.first, edges[road].second.second);
            road++;
        }
        if(same(a, b)) ans[queries[i].first.second]="TAIP";
        else ans[queries[i].first.second]="NE";
    }

    for(auto u : ans){
        cout << u << "\n";
    }
}

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