Submission #1235654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235654		veehj	Drivers (BOI24_drivers)	C++17	100 / 100	387 ms	24048 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(ll i=(ll)(a); i<(ll)(b); i++)
#define rrep(i, a, b) for(ll i=(ll)(a); i>=(ll)(b); i--)
#define vl vector<ll>
#define vpll vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define pll pair<ll, ll>
// Drivers
ll n, m, u;
vvl adj;
vl pa, sz;

ll findpa(ll a){
  if(pa[a]==-1 || pa[a]==a) return a;
  return pa[a]=findpa(pa[a]);
}

void merge(ll a, ll b){
  a=findpa(a); b=findpa(b);
  if(a==b) return;
  if(sz[a]<sz[b]) swap(a, b);
  pa[b]=a;
  sz[a]+=sz[b];
}

void f() {
  cin >> n >> m >> u;
  adj.assign(n, vl(0));
  pa.assign(n, -1);
  sz.assign(n, 1);
  priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> edges;
  rep(i, 0, m){
    ll x, y, t; cin >> x >> y >> t;
    x--; y--; edges.push({t, {x, y}});
  }
  vl a(u), b(u);
  vector<bool> ans(u, 0);
  priority_queue<pll, vpll, greater<pll>> q;
  rep(i, 0, u){
    ll p; cin >> a[i] >> b[i] >> p; a[i]--; b[i]--;
    q.push({p, i});
  }
  while(!q.empty()){
    if(!edges.empty() && edges.top().fi<=q.top().fi){
      merge(edges.top().se.fi, edges.top().se.se);
      edges.pop();
      continue;
    }
    if(findpa(a[q.top().se])==findpa(b[q.top().se])) ans[q.top().se]=1;
    q.pop();
  }
  rep(i, 0, u){
    if(ans[i]) cout << "TAIP";
    else cout << "NE";
    cout << endl;
  }
}

int main() {
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; i++) {
    // cout << '#' << i << endl;
    f();
    cout << endl;
  }
}

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