Submission #1312904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312904		Valenz	Drivers (BOI24_drivers)	C++20	100 / 100	122 ms	21504 KiB

Main

// 道草を楽しめ 大いにな。ほしいものより大切なものが きっとそっちに ころがってる
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t; // available on 64-bit targets
 
//defines
#define int long long
#define debug(x) cerr << "(" << #x << "=" << x << "," << __LINE__ << ")\n";
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);
 
//constants
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; 
const char dir[4]{'D','R','U','L'};
const int maxn=2e5+5;
const double eps=1e-9;
 
//typedefs
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
 
//Template
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <typename T, auto M> struct Mod {
    using V = conditional_t<sizeof(T) <= 4, u64, u128>;
    static V inv(V x, V m) { return x > 1 ? m - inv(m % x, x) * m / x : 1; }
    make_unsigned_t<T> x;
    Mod() : x(0) {}
    Mod(auto y) : x(y % M) { x >= M ? x += M : x; }
    operator T() const { return x; }
    Mod operator-() const { return Mod() -= *this; }
    Mod operator+(auto rhs) const { return Mod(*this) += rhs; }
    Mod operator-(auto rhs) const { return Mod(*this) -= rhs; }
    Mod operator*(auto rhs) const { return Mod(*this) *= rhs; }
    Mod operator/(auto rhs) const { return Mod(*this) /= rhs; }
    Mod &operator+=(Mod rhs) { return (x += rhs.x) >= M ? x -= M : x, *this; }
    Mod &operator-=(Mod rhs) { return (x -= rhs.x) >= M ? x += M : x, *this; }
    Mod &operator*=(Mod rhs) { return x = x * V(rhs.x) % M, *this; }
    Mod &operator/=(Mod rhs) { return x = x * inv(rhs.x, M) % M, *this; }
    Mod pow(auto y) const { // O(log y) | 0^(-inf,0] -> 1
    Mod ans(1), base(*this);
    for (auto e = y < 0 ? ~y + u128(1) : +y; e; e >>= 1, base *= base) {
        e & 1 ? ans *= base : ans;
    }
    return y < 0 ? Mod(1) /= ans : ans;
    }
};
 
using mint = Mod<int, 998244353>;

struct DSU
{
    vector<int> par,sz;
    DSU(int n)
    {
        par.resize(n+1,0);
        sz.resize(n+1,1);
        for(int i=1;i<=n;i++)
        {
            par[i]=i;
        }
    }
    int find_par(int u)
    {
        return par[u]=(u==par[u]?u:find_par(par[u]));
    }
    bool merge(int a,int b)
    {
        int x=find_par(a);
        int y=find_par(b);
        if(x==y)
        {
            return false;
        }
        if(sz[x]>sz[y])
        {
            swap(x,y);
        }
        par[x]=y;
        sz[y]+=sz[x];
        return true;
    }
};
void solve()
{
    int n,m,q;
    cin >> n >> m >> q;
    vector<array<int,3>> a(m);
    for(int i=0;i<m;i++)
    {
        cin >> a[i][1] >> a[i][2] >> a[i][0];
    }
    sort(all(a));
    vector<array<int,4>> qr(q);
    for(int i=0;i<q;i++)
    {
        cin >> qr[i][1] >> qr[i][2] >> qr[i][0];
        qr[i][3]=i;
    }
    sort(all(qr));
    int cur=0;
    DSU dsu(n+1);
    vector<string> ans(q);
    for(int i=0;i<q;i++)
    {
        while(cur<m and a[cur][0]<=qr[i][0])
        {
            dsu.merge(a[cur][1],a[cur][2]);
            cur++;
        }
        if(dsu.find_par(qr[i][1])==dsu.find_par(qr[i][2]))
        {
            ans[qr[i][3]]="TAIP";
        }
        else
        {
            ans[qr[i][3]]="NE";
        }
    }
    for(auto i:ans)
    {
        cout << i << '\n';
    }
}
signed main()
{
    fastio();
    int t=1;
    // cin >> t;
    while(t--)
    {
        solve();
    }

    return 0;
}

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