제출 #1323865

#제출 시각아이디문제언어결과실행 시간메모리
1323865raqin_shahrierDrivers (BOI24_drivers)C++20
100 / 100
289 ms88868 KiB
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// using namespace __gnu_pbds;
 
typedef long long ll;
 
#define int long long
 
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define vpi vector<pair<int,int>>
#define rep(ii,st, n) for(int ii=st; ii<n; ii++)
#define gp " "

//bit_manupulation
#define checkbit(x,n) (x&(1LL<<n))
#define setbit(x,n) (x=(x|(1LL<<n)))
#define resetbit(x,n) (x=(x&(~(1LL<<n))))
#define pow2(i) (1LL<<i)
#define bitcnt(x) ((sizeof(x) <= sizeof(int)) ? (32 - __builtin_clz(x)) : (64 - __builtin_clzll(x)))

// #define DEBG

#define debug(n)
#define debugc(a)
#define debugcc(a)
#ifdef DEBG
#define debug(n) cout<<__LINE__<<gp<<#n<<gp<<n<<endl;
#define debugc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<el<<gp;}cout<<']'<<endl;
#define debugcc(a) cout<<__LINE__<<gp<<#a<<gp<<'['<<gp;for(auto el:a){cout<<'{'<<gp<<el.ff<<','<<el.ss<<gp<<'}'<<gp;}cout<<']'<<endl;
#endif

#define fastcin() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'


#define All(a) a.begin(),a.end()
template<typename T> void get_vector(T&a){for(auto&e:a)cin>>e;}
template<typename T> void put_vector(T a){for(auto e:a)cout<<e<<" ";cout<<endl;}


const ll INF = 2e18;
const ll inf = INT_MAX;
const ll M = 1e9 + 7;
const ll N = 2e5 + 7;
const ll modinvof2 = 500000004;


//==============================CODE STARTS HERE==============================//

struct Edge {
    int u, v, t;
};

vector<vector<pair<int,int>>>g;
const int MAXN = 200005;
const int LOG = 18;

int up[MAXN][LOG], mx[MAXN][LOG], depth[MAXN];
int parent[MAXN];
int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}



// Preprocessing: DFS to fill depths and the first jump (2^0)
void dfs(int u, int p, int w, int d) {
    depth[u] = d;
    up[u][0] = p;
    mx[u][0] = w;
    for (int i = 1; i < LOG; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        mx[u][i] = max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
    }
    for (auto& edge : g[u]) {
        if (edge.ff != p) dfs(edge.ff, u, edge.ss, d + 1);
    }
}

int get_path_max(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int res = 0;
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            res = max(res, mx[u][i]);
            u = up[u][i];
        }
    }
    if (u == v) return res;
    for (int i = LOG - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            res = max({res, mx[u][i], mx[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    return max({res, mx[u][0], mx[v][0]});
}
vector<bool>visited;
map<int,int>mp;
vector<int>current_cc;
void dfs2(int vertex){
    if(visited[vertex]){
        return;
    }
    visited[vertex] = true;
    current_cc.push_back(vertex);
    for(auto& child: g[vertex]){
        dfs2(child.ff);
    }
}

void preprocessing(){

}

void solve(int testcases){
    int n,m,q;
    cin>>n>>m>>q;
    vector<Edge>edges(m);
    g.resize(N);
    visited.resize(n+7);
    for(int i = 0; i<m; i++){
      cin>>edges[i].u>>edges[i].v>>edges[i].t;
    }
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.t < b.t; });
    for (int i = 1; i <= N; i++) parent[i] = i;
    int edges_count = 0;
    for (auto& e : edges) {
        int root_u = find_set(e.u);
        int root_v = find_set(e.v);
        if (root_u != root_v) {
            parent[root_u] = root_v;
            g[e.u].push_back({e.v, e.t});
            g[e.v].push_back({e.u, e.t});
            edges_count++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (depth[i] == 0) dfs(i, i, 0, 1);
    }
    // exit(0);
    while(q--){
      int a,b,p;
      cin>>a>>b>>p;
      if (find_set(a) != find_set(b)) {
            cout << "NE" << "\n"; 
        } else {
            cout << (get_path_max(a, b) <= p ? "TAIP" : "NE") << "\n";
        }
    }

}

int32_t main(){
    fastcin();

    int t=1;
    // cin>>t;
    preprocessing();
    rep(i,1,t+1){
       solve(i);
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve(long long int)':
Main.cpp:138:44: warning: iteration 200004 invokes undefined behavior [-Waggressive-loop-optimizations]
  138 |     for (int i = 1; i <= N; i++) parent[i] = i;
      |                                  ~~~~~~~~~~^~~
Main.cpp:138:23: note: within this loop
  138 |     for (int i = 1; i <= N; i++) parent[i] = i;
      |                     ~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...