제출 #1333591

#제출 시각아이디문제언어결과실행 시간메모리
1333591sporknivesWind Turbines (EGOI25_windturbines)C++20
8 / 100
312 ms6076 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;

int n;
/*vector<int> par, rnk;
void init(int n) {
	par.resize(n); for(int i=0;i<n;i++) par[i]=i;
	rnk.resize(n); for(int i=0;i<n;i++) rnk[i]=1;
}

int root(int n) {
	if(par[n]==n) return n;
	else par[n] = root(par[n]);
	return par[n];
}

void merge(int a, int b) {
	int pa = root(a), pb = root(b);
	if(rnk[pa] >= rnk[pb]) {
		par[pb]=pa;
		if(rnk[pa]==rnk[pb]) rnk[pa]++;
	}
	else {
		par[pa]=pb;
	}
}

bool sameSet(int a, int b) {
	return root(a) == root(b);
}

int find_mst(vector<pair<int,pii>> edges, vector<int> src) {
	init(n);
	for(int i=0;i<src.size()-1;i++) {
		merge(src[i],src[i+1]);
	}
	
	//sort(edges.begin(),edges.end());
	vector<pii> mst;
	int cost=0;
	for(pair<int,pii> x: edges) {
		int w = x.first, a = x.second.first, b = x.second.second;
		if(!sameSet(a,b)) {
			mst.push_back({a,b});
			cost+=w;
			merge(a,b);
		}
	}
	
	return cost;
}*/

signed main() {
	int m,q; cin>>n>>m>>q;
	//vector<pair<int,pii>> edges(m);
	int edges[n-1];
	for(int i=0;i<m;i++) {
		int a,b,w; cin>>a>>b>>w;
		//edges[i] = {w,{a,b}};
		if(a>b)swap(a,b);
		edges[a]=w;
	}
	
	int psum[n]; psum[0]=0; int cur=0;
	for(int i=0;i<n-1;i++) {
		cur+=edges[i];
		psum[i+1]=cur;
	}
	//sort(edges.begin(),edges.end());
	for(int i=0;i<q;i++) {
		int l,r; cin>>l>>r;
		/*vector<int> src;
		for(int j=l;j<=r;j++) {
			src.push_back(j);
		}
		cout<<find_mst(edges, src)<<"\n";*/
		
		cout<<psum[l]+psum[n-1]-psum[r]<<"\n";
	}
	return 0;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...