Submission #1235797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235797		jundi	Drivers (BOI24_drivers)	C++20	0 / 100	0 ms	468 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<pair<int,int>> p(n);
    DisjointSet ds(n);
    vector<int> length(n);
    vector<pair<int,int>> g[n];
    for(int i=0;i<m;i++){
        cin>>p[i].fi>>p[i].se;
        p[i].fi--; p[i].se--;
        cin>>length[i];
        ds.unionByRank(p[i].fi,p[i].se);
        g[p[i].fi].push_back({p[i].se,length[i]});
        g[p[i].se].push_back({p[i].fi,length[i]});
    }

    vector<int> par;
    map<int,int> remap;
    int cnt=0;
    for (int i=0;i<n;i++) {
        int r=ds.findUPar(i);
        if (remap.find(r)==remap.end()){ 
            remap[r]=cnt;
            par.push_back(r);
            cnt++;
        }
    }
    // for(int i=0;i<cnt;i++) cout<<par[i]<<" ";
    vector<int> distTo(n,1e9);
    for(int i=0;i<cnt;i++){
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>> pq;
	    distTo[par[i]]=0;
	    pq.push(make_pair(par[i],par[i]));
	    while(!pq.empty()){
		    int dist=pq.top().fi;
		    int prev=pq.top().se;
		    pq.pop();
		    vector<pair<int,int>>::iterator it;
		    for( it = g[prev].begin() ; it != g[prev].end() ; it++){
			    int next = it->first;
			    int nextDist = it->second;
			    if( distTo[next] > distTo[prev] + nextDist){
			    	distTo[next] = distTo[prev] + nextDist;
			    	pq.push(make_pair(distTo[next], next));
			    }
		    }
	    }
	    // for(int i=0;i<n ; i++)	cout << distTo[i] << " ";
        // cout<<endl;
    }
    // cout<<endl;

    int u,v,t;
    for(int i=0;i<q;i++){
        cin>>u>>v>>t;
        u--; v--;
        if(ds.findUPar(u)!=ds.findUPar(v)) cout<<"NE"<<endl;
        else if(abs(distTo[u]-distTo[v])<=t) cout<<"TAIP"<<endl;
        else cout<<"NE"<<endl;

    }
}

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