Submission #1304383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304383		baktrr	Drivers (BOI24_drivers)	C++20	100 / 100	138 ms	23216 KiB

Main

/**
  III     U   U  N   N  DDDD   EEEEE  RRRR   SSSS  TTTTT  AAAAA  N   N  DDDD      I  TTTTT     N   N   OOO   W   W
   I      U   U  NN  N  D   D  E      R   R  S       T    A   A  NN  N  D   D     I    T       NN  N  O   O  W   W
   I      U   U  N N N  D   D  EEEE   RRRR   SSSS    T    AAAAA  N N N  D   D     I    T       N N N  O   O  W W W
   I      U   U  N  NN  D   D  E      R  R      S    T    A   A  N  NN  D   D     I    T       N  NN  O   O  WW WW
  III     UUUUU  N   N  DDDD   EEEEE  R   R  SSSS    T    A   A  N   N  DDDD      I    T       N   N   OOO   W   W
**/

//18.09.25
#include <bits/stdc++.h>

// #pragma optimize("g", on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroint-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define F first
#define ent '\n'
#define S second
#define no "NO\n"
#define in insert
#define yes "YES\n"
#define pp pop_back
#define pb push_back
#define int long long
#define sz(w) w.size()
#define pii pair <int, int>
#define all(w) w.begin(), w.end()
#define rall(w) w.rbegin(), w.rend()
#define Yeah ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MOD = 998244353, M = 4e5 + 7, N = 2e5 + 7, INF = 1e18, inf = 1e9 + 7, LOG = 20 , mod = 1e9 + 7 ;

// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int p[N] , len[N] ;

vector <pii> g[N] ;

int find(int v) {
    if(v == p[v]) {
        return v; 
    }
    return p[v] = find(p[v]) ;
}

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

struct net {
    int a , b , t , id ;
};

struct ten {
    int u , v , x , idx ;
};

bool cmp(net i , net j) {
    return i.t < j.t ;
}

bool cmp1(ten i , ten j) {
    return i.x < j.x ;
}

void accepted() {
    int n, m , k ;
    cin >> n >> m >> k ;
    for(int i = 1 ; i <= n ; i++) {
        p[i] = i ;
        len[i] = 1 ;
    }
    vector <net> v ;
    for(int i = 1 ; i <= m ; i++) {
        int a , b , t ;
        cin >> a >> b >> t;
        v.pb({a , b , t , i}) ;
    }
    vector <ten> v1 ;
    for(int i = 1 ; i <= k ; i++) {
        int a , b , x ;
        cin >> a >> b >> x ;
        v1.pb({a , b , x , i}) ;
    }
    sort(all(v) , cmp) ;
    sort(all(v1) , cmp1) ;
    int i = 0 ;
    string ans[k + 1] ;
    for(auto [u , to , x , idx] : v1) {
        while(v[i].t <= x && i < m) {
            unite(v[i].a , v[i].b) ;
            i++;
        }
        if(find(u) == find(to)) {
            ans[idx] = "TAIP" ;
        }
        else {
            ans[idx] = "NE" ;
        }
    }
    for(int i = 1 ; i <= k ; i++) {
        cout << ans[i] << ent ;
    }
}


signed main() {
    Yeah
 
    // PLS NeverGiveUp

    // freopen("cowpatibility.in", "r", stdin) ;  
    // freopen("cowpatibility.out", "w", stdout) ;
    
    int T = 1 ;
    // cin >> T ;
    while(T--) {
        accepted();
        cout << endl ;
    }
}

/**



**/

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