Submission #1249325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249325		amanthaband	Drivers (BOI24_drivers)	C++20	100 / 100	356 ms	17624 KiB

Main

#include <bits/stdc++.h>
#include <tuple>
using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define rrep(i,a,b) for(int i = a; i >= b; --i)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<ll> vll;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;

const ll INF = 1e9+5;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const int MOD2 = 998244353;

template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxpq = priority_queue<T>;

struct DSU {
    vi p, sz, mn;

    void init(int n) {
        p.resize(n);
        sz.assign(n, 1);
        mn.resize(n);
        iota(all(p), 0);
        iota(all(mn), 0);
    }

    int find(int x) {
        return x == p[x] ? x : p[x] = find(p[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return sz[find(x)];
    }

    int get_min(int x) {
        return mn[find(x)];
    }

    bool join(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        if (sz[x] < sz[y]) swap(x, y);
        p[y] = x;
        sz[x] += sz[y];
        mn[x] = min(mn[x], mn[y]);
        return true;
    }
};

int main() {
    DSU dsu;
    int n,m,u;
    cin>>n>>m>>u;
    vector<tuple<int, int, int>> v(m);
    for(int i = 0; i < m; i++) {
        int x,y,t;
        cin>>x>>y>>t;
        v[i] = make_tuple(t,x,y);
    }
    sort(all(v));

    vector<tuple<int,int,int,int>> uv(u);

    for(int i = 0; i < u; i++) {
        int a,b,p;
        cin>>a>>b>>p;
        uv[i] = make_tuple(p,a,b,i);
    }
    sort(all(uv));

    int ro = 0;
    vector<string> ans(u);
    dsu.init(n+1);
    for (auto [p,a,b,i] : uv) {
        while (ro < m) {
            int t,x,y;
            tie(t,x,y) = v[ro];
            if (t > p) break;
            dsu.join(x,y);
            ro++;
        }

        ans[i] = dsu.same(a,b) ? "TAIP" : "NE";

    }
    for(int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<endl;
    }




    return 0;
}

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