Submission #389842

#	Time	Username	Problem	Language	Result	Execution time	Memory
389842		gouravkhunger	Sightseeing (NOI14_sightseeing)	C++17	0 / 25	3554 ms	39364 KiB

sightseeing

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vll;
typedef set<int> si;
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int>> pqs;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define FOR(i, a, b) for (int i=a; i<=b; i++)
#define FORn(i, a, b) for (int i=a; i>=b; i--)
#define all(v) v.begin(), v.end()
#define allR(v) v.rbegin(), v.rend()
#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

const int MOD = 1e9+7;
const ll INF = 1e15;
struct UFDS {
    int n;
    vector<int> sz, par;
    void init(int x) {
        n = x;
        par.resize(n+1);
        sz.resize(n+1, 1);
        iota(par.begin(), par.end(), 0);
    }
    int find(int v) { return par[v] == v ? v : par[v] = find(par[v]); }
    bool join(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return false;
        if(sz[a] < sz[b])
            swap(a, b);
        par[b] = a;
        sz[a]+=sz[b];
        return true;
    }
};

int main() {
	
	FIO;
	
	int v,e,q;
	cin>>v>>e>>q;
	
	vector<pair<int, pii>> edges(e);
	
	FOR(i, 0, e-1) {
		cin>>edges[i].S.F>>edges[i].S.S>>edges[i].F;
	}
	
	sort(all(edges), greater<pair<int,pii>>());
	
	/*for(auto e : edges){
		cout<<e.S.F<<" "<<e.S.S<<" "<<e.F<<"\n";
	}*/
	
	int qe;
	UFDS u;
	while(q--){
		
		cin>>qe;
		int cost = 0;

		u.init(v);
		
		for(auto e : edges) {
			
			if(u.join(e.S.F, e.S.S)) cost+=e.F;
			
			if(u.find(1)==u.find(qe)) break;
		}
		
		cout<<cost<<"\n";
		
	}
	
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 10