| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 671703 |
2022-12-13T15:21:18 Z |
smartmonky |
Money (IZhO17_money) |
C++14 |
|
1500 ms |
8148 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
const int N = 1e5 + 10;
int d[N], ans[N], par[N], sz[N];
vector < pair <int,int> > g[N];
set <int> s[N];
int n;
int vis[N];
int find(int a){
if(par[a] == a)
return a;
return par[a] = find(par[a]);
}
void connect(int a, int b, int w){
a = find(a);
b = find(b);
if(a == b)return;
par[b] = a;
sz[b] += sz[a];
if ((int) s[a].size() > (int) s[b].size()) swap(s[a] , s[b]);
for (auto x : s[b])
{
if (s[a].find(x) != s[a].end())
{
ans[x] = w;
s[a].erase(x);
}
else
{
s[a].insert(x);
}
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(d, 0x3f3f3f, sizeof(d));
int m;
cin >> n >> m;
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
g[a].pb({b, c});
g[b].pb({a, c});
}
int k;
cin >> k;
set <pair <int,int> > st;
for(int i = 0; i < k; i++){
int a;
cin >> a;
st.insert({0, a});
d[a] = 0;
}
while (!st.empty()){
int v = st.begin()->second;
st.erase (st.begin());
for (size_t j=0; j<g[v].size(); ++j) {
int to = g[v][j].first,
len = g[v][j].second;
if (d[v] + len < d[to]) {
st.erase (make_pair (d[to], to));
d[to] = d[v] + len;
st.insert (make_pair (d[to], to));
}
}
}
vector <pair <int,int> > vp;
for(int i = 1; i <= n; i++){
vp.pb({d[i], i});
}
int q;
cin >> q;
for(int i = 1; i <= q; i++){
int a, b;
cin >> a >> b;
s[a].insert(i);
s[b].insert(i);
}
sort(rall(vp));
for (auto x : vp){
int w = x.first , u = x.second;
vis[u] = 1;
for (auto adj : g[u])
{
int v = adj.ff;
if (vis[v])
connect(u , v , w);
}
}
for(int i = 1; i <= q; i++)cout << ans[i] << endl;
}
Compilation message
money.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
43 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1583 ms |
8148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1583 ms |
8148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1583 ms |
8148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1583 ms |
8148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
