Submission #1313009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313009		lev	Sightseeing (NOI14_sightseeing)	C++20	15 / 25	830 ms	49612 KiB

sightseeing

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, N, m, q, par[mn], val[mn];
vector <int> a[mn];
vector <array<int, 3>> edge;

void init(){
	for(int i = 1; i <= n; i++) par[i] = i;
}

int find(int u){
	if(u == par[u]) return u;
	return par[u] = find(par[u]);
}

void join(int u, int v, int w){
	u = find(u), v = find(v);
	if(u == v) return;
	++ N;
	par[u] = par[v] = par[N] = N;
	a[N].push_back(u);
	a[N].push_back(v);
	val[N] = w;
}

int up[mn][20], d[mn];

void dfs(int u){
	for(auto v : a[u]){
		debug(u, v);
		up[v][0] = u;
		d[v] = d[u] + 1;
		dfs(v);
	}
}

void build(){
	for(int j = 1; j < 20; j++){
		for(int i = 1; i <= N; i++){
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);
	for(int i = 19; i >= 0; i--){
		if(d[up[u][i]] >= d[v]) u = up[u][i];
	}
	if(u == v) return u;
	for(int i = 19; i >= 0; i--){
		if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
	}
	return up[u][0];
}

void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
    	int u, v, w; cin >> u >> v >> w;
    	edge.push_back({w, u, v});
    }
    sort(all(edge)); reverse(all(edge));

    N = n; init();

    for(auto [w, u, v] : edge) join(u, v, w);
    dfs(N); build();
	while(q--){
		int v; cin >> v;
		debug(v, lca(1, v));
		cout << val[lca(1, v)] << '\n';
	}

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #define task "Kawabata"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

Compilation message (stderr)

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sightseeing.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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