Submission #1235832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235832		jundi	Drivers (BOI24_drivers)	C++20	100 / 100	358 ms	14980 KiB

Main

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

#define fi first
#define se second

class DisjointSet{
    vector<int> rank,parent;
public:
    DisjointSet(int n){ 
        rank.resize(n+1,0);
        parent.resize(n+1);
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    int findUPar(int node){  
        if(node== parent[node]) return node;
        else return parent[node]=findUPar(parent[node]);
    }
    void unionByRank(int u,int v){
        int pu=findUPar(u);
        int pv=findUPar(v);
        if(pu==pv) return;
        if(rank[pu]<rank[pv]){
            parent[pu]=pv;
        }
        else if(rank[pu]>rank[pv]){
            parent[pv]=pu;
        }
        else{
            parent[pv]=pu;
            rank[pu]++;
        }
    }
};

int main(){
    int n,m,q;
    cin>>n>>m>>q;

    vector<tuple<int,int,int>> edge;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--; b--;
        edge.push_back({c,a,b});
    }

    vector<tuple<int,int,int,int>> qq;
    for(int i=0;i<q;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--; b--;
        qq.push_back({c,a,b,i});
    }

    sort(qq.begin(),qq.end());
    sort(edge.begin(),edge.end());

    DisjointSet ds(n);
    vector<string> ans(q);
    int index=0;
    for(int i=0;i<q;i++){
        while( index < m && get<0>(edge[index]) <= get<0>(qq[i])){
            int u=get<1>(edge[index]);
            int v=get<2>(edge[index]);
            ds.unionByRank(u,v);
            index++;
        }
        int u=get<1>(qq[i]);
        int v=get<2>(qq[i]);
        if(ds.findUPar(u)==ds.findUPar(v)) ans[get<3>(qq[i])]="TAIP";
        else ans[get<3>(qq[i])]="NE";
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<endl;
    }
}

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