Submission #566004

#TimeUsernameProblemLanguageResultExecution timeMemory
566004UzoufEvacuation plan (IZhO18_plan)C++14
100 / 100
508 ms46264 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define endl "\n" int mod=1e9+7; const int N=1e5+5;//2e5+5; template<class x> using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>; vector<vector<pair<int,int> > > tst(N),v(N); vector<vector<int> > grp(N); pair<int,int> dis[N]; int npp[N],par[N],ans[N]; bool vis[N]; void con(int a,int b,int cst) { a=par[a]; b=par[b]; if (grp[a].size()>grp[b].size()) swap(a,b); for (int i:grp[a]) { for (auto j=0;j<tst[i].size();j++) { if (par[tst[i][j].first]==b) ans[tst[i][j].second]=cst; } } for (int i:grp[a]) { par[i]=b; grp[b].push_back(i); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(".in", "r", stdin); freopen(".out", "w", stdout); int n,m; cin>>n>>m; while (m--) { int a,b,c; cin>>a>>b>>c; v[a].push_back({c,b}); v[b].push_back({c,a}); } int k; cin>>k; for (int i=0;i<k;i++) cin>>npp[i]; for (int i=1;i<=n;i++) { dis[i]={1e10,i}; } priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; for (int i=0;i<k;i++) { dis[npp[i]]={0,npp[i]}; q.push({0,npp[i]}); } while (!q.empty()) { int cnt=q.top().first; int node=q.top().second; q.pop(); if (dis[node].first<cnt) {continue;} for (int i=0;i<v[node].size();i++) { int price=v[node][i].first; int child=v[node][i].second; if (dis[child].first>(cnt+price)) { dis[child].first=cnt+price; q.push(dis[child]); } } } int t; cin>>t; for (int i=0;i<t;i++) { int a,b; cin>>a>>b; tst[a].push_back({b,i}); tst[b].push_back({a,i}); } sort(dis,dis+N); reverse(dis,dis+N); for (int i=1;i<=n;i++) { par[i]=i; grp[i].push_back(i); } for (int i=0;i<n;i++) { int dd=dis[i].first,nm=dis[i].second; for (int j=0;j<v[nm].size();j++) { if (vis[v[nm][j].second] && par[v[nm][j].second]!=par[nm]) { con(nm,v[nm][j].second,dd); } } vis[nm]=true; } for (int i=0;i<t;i++) cout<<ans[i]<<endl; }

Compilation message (stderr)

plan.cpp: In function 'void con(long long int, long long int, long long int)':
plan.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (auto j=0;j<tst[i].size();j++) {
      |                   ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:64:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int i=0;i<v[node].size();i++)
      |                      ~^~~~~~~~~~~~~~~
plan.cpp:90:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |       for (int j=0;j<v[nm].size();j++) {
      |                    ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...