#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 int
//#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 int 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
}
}
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>///
//weight final vertex
vector<vector<pair<int,int>>> adj;
int n;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
#define trav(a,x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
#define int long long
struct DSU {
vi e; void init(int N) { e = vi(N,-1); }
// get representive component, uses path compression
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool sameSet(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y); if (x == y) return 0;
if (e[x] > e[y]) swap(x,y);
e[x] += e[y]; e[y] = x; return 1;
}
};
int comp;
template<class T> T kruskal(int N, vector<pair<T,pi>> ed) {
sort(all(ed));
reverse(all(ed));
T ans = 0; DSU D; D.init(N); // edges that unite are in MST
trav(a,ed)
if (D.unite(a.s.f,a.s.s)) {
adj[a.s.f].pb({a.f,a.s.s});
adj[a.s.s].pb({a.f,a.s.f});
cerr<<a.s.f<<" "<<a.s.s<<" >="<<a.f<<"\n";
comp--;
}
return ans;
}
vector<int> ans;
signed main(){
setIO("");
int n,m,q;cin>>n>>m>>q;
adj.resize(n+2);
ans.resize(n+2, INF);
vector<pair<ll,pi>> edge;
for (int i = 0; i < m; i++){
int a, b; ll c;
cin >> a >> b >> c;
edge.push_back(mp(c, mp(a, b)));
}
comp = n;
ll ansss = kruskal(n, edge);
ans[1]=INF;
function<void(int v, int p, int mx)> dfs = [&] (int v, int p, int mx) {
ans[v] = min(ans[v], mx);
for(auto tx : adj[v]) if(tx.s != p) {
dfs(tx.s, v, min(tx.f, mx));
}
};
dfs(1, -1, INF);
while(q--){
int x;cin>>x;
cout<<ans[x]<<"\n";
}
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
sightseeing.cpp:65: warning: "int" redefined
65 | #define int long long
|
sightseeing.cpp:17: note: this is the location of the previous definition
17 | #define int long long int
|
sightseeing.cpp: In function 'int main()':
sightseeing.cpp:109:8: warning: unused variable 'ansss' [-Wunused-variable]
109 | ll ansss = kruskal(n, edge);
| ^~~~~
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); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
876 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
502 ms |
12584 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3586 ms |
168204 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
