Submission #322157

#	Time	Username	Problem	Language	Result	Execution time	Memory
322157		prasanth30	Sightseeing (NOI14_sightseeing)	C++14	0 / 25	1806 ms	110448 KiB

sightseeing

#include <bits/stdc++.h>
using namespace std;
//actual solution is at bottom//
////<pbds>////
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
    rb_tree_tag, tree_order_statistics_node_update>; 
// change null_type for map
// change less to less_equal for multiset
#define ook order_of_key
#define fbo find_by_order*/
///</pbds>///

#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define google(i) cout<<"Case #"<<i<<" :";
///<constants>///
const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = 4*atan((ld)1); 
const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
///</constants>///

///<IO>/// 
namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace io;
///</IO>///

///<execution-time>///
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
/*example for clock usage
    clock_t z = clock();
    debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
*/
///</execution-time>///
struct UFDS {
    int n, c;
    vector<int> len, par;
    void init(int x, int y = 1) {
        n = x;
        c = y;
        par.resize(n+2);
        len.assign(n+2, 1);
        iota(par.begin(), par.end(), 0);
    }
    int fin(int v) { return par[v] == v ? v : par[v] = fin(par[v]); }
    bool join(int a, int b) {
        a = fin(a); b = fin(b);
        if(a == b) return false;
        if(rng() % 2) swap(a, b);
        if(c && len[a] < len[b])
            swap(a, b);
        par[b] = a;
        if(c) len[a] += len[b];
        return true;
    }
    int szz(int x) { return len[fin(x)]; }
};

int n, m, q;
vector<vector<pair<int,int>>> mst;
vector<pair<int,pair<int,int>>> initial;
vector<int> ans;
void init(){
	cin>>n>>m>>q;
    mst.resize(n+2);
    ans.resize(n+1);
    ans.assign(sizeof(ans),INF);
    for(int i = 0; i < m ; ++i){
    	int u, v, w;
    	cin>> u >> v >> w;
    	initial.push_back({ w , {u , v} });
    }
    sort( initial.begin(), initial.end() ,greater<pair<int,pair<int,int>>>());
}
void kruskal(){
	UFDS dsu;
    dsu.init(n);
    for(auto a: initial){
    	int weight = a.first;
    	int from = a.second.first;
    	int to= a.second.second;
    	if( dsu.join(from,to) ){
    		mst[from].push_back({weight,to});
    		mst[to].push_back({weight,from});
    	}
    }
}
void dfs(int u,int par,int mxx){
	ans[u]=min( ans[u] , mxx);
	for(auto i:mst[u]){
		if( i.second != par)
			dfs(i.second, u , min( i.first , mxx));
	}
}
void query(){
	while(q--){
		int xx;
		cin >> xx;
		cout << ans[xx] << "\n";
	}
}
signed main(){
    setIO("");
    init();
    kruskal();
    dfs(1,-1,INF);
    query();
    return 0;
}
/* stuff you should look for
    * check whether you have read the problem correctly
    * int overflow, array bounds
    * special cases (n=1?), slow multiset operations
    * do smth instead of nothing and stay organized
*/

Compilation message (stderr)

sightseeing.cpp: In function 'void io::setIn(std::string)':
sightseeing.cpp:34:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp: In function 'void io::setOut(std::string)':
sightseeing.cpp:35:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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