Submission #634848

#TimeUsernameProblemLanguageResultExecution timeMemory
634848drkarlicio2107Evacuation plan (IZhO18_plan)C++14
19 / 100
761 ms38588 KiB
#include <bits/stdc++.h> using namespace std; vector < pair <int, long long int> > g [100010]; long long int dist [100010]; set < pair <long long int, long long int> > s; long long int P [100010]; long long int d [100010]; long long int bio [100010]; vector <pair <int, int> > qr [100010]; long long int ans [100010]; long long int vis [100010]; vector < pair <long long int, long long int> > kr; long long int p ( long long int x) { return (P[x]!=x ? P [x]=p (P[x]) : P[x]); } ; long long int W; void spoji ( long long int x, long long int y){ x=p (x); y=p (y); if (x==y) return ; if (qr [x].size()<qr [y].size()) swap (x, y); P [y]=x; for ( long long int i=0; i<qr [y].size(); i++){ if (p (y)==p(qr[y][i].first)) ans [qr[y][i].second]=max (ans [qr[y][i].second], W); else qr [x].push_back ({qr[y][i].first, qr[y][i].second}); } return ; } int main(){ long long int n, m; cin >> n >> m; for ( long long int i=1; i<n+1; i++){ dist [i]=(int)1e18; P [i]=i; d[i]=1; } //for ( long long int i=1; i<n+1; i++) s.insert ({dist [i], i}); for ( long long int i=0; i<m; i++){ long long int a, b, c; cin >> a >> b >> c; g [a].push_back ({b, c}); g [b].push_back ({a, c}); } long long int k; cin >> k; for ( long long int i=0; i<k; i++){ long long int a; cin >> a; //s.erase ({dist [a], a}); dist [a]=0; s.insert ({dist [a], a}); } for ( long long int j=0; j<n-k; j++){ long long int x=(*s.begin()).second; if ((*s.begin()).first!=dist [x]) continue; s.erase ({dist [x], x}); for ( long long int i=0; i<g [x].size(); i++){ long long int y=g [x][i].first; if (dist [y]>dist [x]+g [x][i].second){ s.erase ({dist [y], y}); dist [y]=dist [x]+g [x][i].second; s.insert ({dist [y], y}); } } } long long int q; cin >> q; for ( long long int i=0; i<q; i++){ long long int x, y; cin >> x >> y; qr [x].push_back ({y, i}); qr [y].push_back ({x, i}); } for ( long long int i=1; i<n+1; i++) { //cout << dist [i] << " "; kr.push_back ({dist [i], i}); } //cout << endl; sort (kr.begin(), kr.end(), greater < pair <long long int, long long int> > ()); for ( long long int i=0; i<kr.size(); i++){ long long int x=kr [i].second; W=kr [i].first; vis [x]=1; for ( long long int j=0; j<g [x].size(); j++){ long long int y=g [x][j].first; if (vis [y]){ spoji (x, y); } } } for ( long long int i=0; i<q; i++) cout << ans [i] << endl; return 0; }

Compilation message (stderr)

plan.cpp: In function 'void spoji(long long int, long long int)':
plan.cpp:16:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for ( long long int i=0; i<qr [y].size(); i++){
      |                           ~^~~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:44:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for ( long long int i=0; i<g [x].size(); i++){
      |                            ~^~~~~~~~~~~~~
plan.cpp:65:28: 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]
   65 |  for ( long long int i=0; i<kr.size(); i++){
      |                           ~^~~~~~~~~~
plan.cpp:67:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for ( long long int j=0; j<g [x].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...