Submission #1265570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265570		herominhsteve	Drivers (BOI24_drivers)	C++20	100 / 100	137 ms	29432 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

struct Edges{
	int u,v,w;
	Edges(int U=0,int V=0,int W=0){
		u=U;
		v=V;
		w=W;
	}
	bool operator < (const Edges &x) const{
		return w<x.w;
	}
};

struct DSU{
	int n;
	vector<int> parent,power;
	DSU(int N=0){
		n=N;
		if (n>0){
			parent.resize(n+1,0);
			power.resize(n+1,1);
		}
	}
	void make_set(){
		for (int i=1;i<=n;i++){
			parent[i]=i;
			power[i]=1;
		}
	}
	int find(int u){
		if (u==parent[u]) return u;
		return parent[u]=find(parent[u]);
	}
	bool Union(int u,int v){
		u=find(u);
		v=find(v);
		if (u==v) return false;
		if (power[u]<power[v]) swap(u,v);
		parent[v]=u;
		power[u]+=power[v];
		return true;
	}
};

DSU dsu;

int n,m,q;
vector<Edges> edges,queries;

void init(){
	cin>>n>>m>>q;
	dsu = DSU(n);
	edges.resize(m);
	for (Edges &x: edges) cin>>x.u>>x.v>>x.w;
	queries.resize(q);
	for (Edges &x: queries) cin>>x.u>>x.v>>x.w;
}

void sol(){
	vector<int> weights;
	for (Edges x: edges) weights.push_back(x.w);
	for (Edges x: queries) weights.push_back(x.w);
	sort(allof(weights));
	weights.resize(unique(allof(weights))-weights.begin());
	int wz = weights.size();
	vector<vector<int>> eByW(wz+1), qByW(wz+1);
	for (int i=0;i<m;i++){
		int eID = lower_bound(allof(weights),edges[i].w) - weights.begin() + 1;
		eByW[eID].push_back(i);
	}
	for (int i=0;i<q;i++){
		int qID = lower_bound(allof(weights),queries[i].w) - weights.begin() + 1;
		qByW[qID].push_back(i);
	}
	dsu.make_set();
	vector<bool> res(q);
	for (int w=0;w<=wz;w++){
		for (int eID : eByW[w]) dsu.Union(edges[eID].u,edges[eID].v);
		for (int qID : qByW[w]) res[qID] = (dsu.find(queries[qID].u) == dsu.find(queries[qID].v));
	}
	for (bool x : res) cout<< (x ? "TAIP\n" : "NE\n");
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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