제출 #1304378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304378		BilAktauAlmansur	Drivers (BOI24_drivers)	C++20	100 / 100	133 ms	29928 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const int N = 3e5 + 7, mod = 998244353;

int n, m, q, p[N], sz[N];
string ans[N];
int get(int v) {
    if(p[v] == v)return v;
    else return p[v] = get(p[v]);
}
void unite(int x, int y) {
    x = get(x), y = get(y);
    if(sz[x] < sz[y])swap(x, y);
    sz[x] += sz[y];
    p[y] = x;
}
void solve() {
    cin>>n>>m>>q;
    for(int i = 1; i <= n; i++)sz[i] = 1, p[i] = i;
    vector<array<int, 3> > vec;
    for(int i = 1, x, y, w; i <= m; i++) {
        cin>>x>>y>>w;
        vec.push_back({w, x, y});
    }
    vector<array<int, 4> > qr;
    for(int i = 1, x, y, w; i <= q; i++) {
        cin>>x>>y>>w;
        qr.push_back({w, x, y, i});
    }
    sort(vec.begin(), vec.end());
    sort(qr.begin(), qr.end());
    int lx = 0;
    for(auto [w, x, y, j] : qr) {
        while(lx < vec.size()) {
            if(vec[lx][0] <= w) {
                unite(vec[lx][1], vec[lx][2]);
                lx ++;
            }else break;
        }
        if(get(x) == get(y))ans[j] = "TAIP";
        else ans[j] = "NE";
    }
    for(int i = 1; i <= q; i++)cout << ans[i] << '\n';
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T = 1;
    // cin>>T;
    while(T --)solve();
}

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