Submission #1146018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146018		dosts	Drivers (BOI24_drivers)	C++20	100 / 100	111 ms	20388 KiB

Main

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 4001,MOD = 1e9+7,B = 250;


struct Query {
    int c,id,a,b;
};

struct DSU {
    vi dad;
    vi sz;

    DSU(int nn) {
        dad.resize(nn+1);
        iota(all(dad),0ll);
        sz.assign(nn+1,1);
    }

    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    } 

    void unite(int a,int b) {
        int x = find(a),y = find(b);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x,y);
        sz[y]+=sz[x];
        dad[x] = y;
    }
};
void solve() { 
    int n,m,q;
    cin >> n >> m >> q;
    DSU dsu(n);
    vector<pair<int,pii>> edg;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edg.push_back({c,{a,b}});
    }
    sort(all(edg));
    vector<Query> qs;
    for (int i=1;i<=q;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        qs.push_back({c,i,a,b});
    }
    sort(all(qs),[&](const Query& q1,const Query& q2) {
        return q1.c < q2.c;
    });
    int ptr = 0;
    vi ans(q+1);
    for (auto it : qs) {
        while (ptr < edg.size() && edg[ptr].first <= it.c) {
            dsu.unite(edg[ptr].ss.ff,edg[ptr].ss.ss);
            ptr++;
        }
        ans[it.id] = (dsu.find(it.a) == dsu.find(it.b));
    }
    for (int i=1;i<=q;i++) cout << (ans[i]?"TAIP\n":"NE\n");
}

int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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