Submission #1022436

#TimeUsernameProblemLanguageResultExecution timeMemory
1022436hasan2006Evacuation plan (IZhO18_plan)C++17
0 / 100
4 ms2652 KiB
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define int long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e5 + 9 , mod = 1e9 + 7; ll a[N]; ll n , m , q , k; vector<pair<int,int>>v[N]; set<pair<int,int>>st; void dijkstra(){ while(st.size()){ auto it = st.begin(); ll x = it->se; ll y = it->fi; st.erase(it); if(a[x] != y) continue; for(auto to : v[x]){ if(a[x] + to.se < a[to.fi]){ a[to.fi] = a[x] + to.se; st.insert({a[to.fi] , to.fi}); } } } } ll sz[N] , p[N] , mn[N]; int get(int n) { while(p[n] != n) n = p[n]; return p[n]; } void join(int x , int y , int k){ x = get(x); y = get(y); if(x != y){ if(sz[x] < sz[y]) swap(x , y); p[y] = x; mn[y] = k; sz[x] += sz[y]; } } void get1(int x , int y){ while(true){ if(sz[x] < sz[y]){ if(p[x] == y){ cout<<mn[x]<<"\n"; return; } x = p[x]; }else{ if(p[y] == x){ cout<<mn[y]<<"\n"; return; } y = p[y]; } if(x == y){ cout<<0<<"\n"; return; } } } void solve() { cin>>n>>m; for(int i = 1; i <= m; i++){ int x , y , z; cin>>x>>y>>z; v[x].pb({y , z}); v[y].pb({x , z}); } cin>>k; for(int i = 1; i <= n; i++){ a[i] = 1e9; } while(k--){ int x; cin>>x; a[x] = 0; st.insert({0 , x}); } dijkstra(); vector<pair<int,int>>g; for(int i = 1; i <= n; i++){ p[i] = i; sz[i] = 1; g.push_back({a[i] , i}); } sort(rall(g)); for(auto i : g){ for(auto to : v[i.se]){ if(a[to.fi] >= a[i.se]){ join(i.se , to.fi , a[i.se]); } } } cin>>q; while(q--){ int x , y; cin>>x>>y; get1(x , y); } } signed main(){ TL; #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن

Compilation message (stderr)

plan.cpp: In function 'long long int get(long long int)':
plan.cpp:49:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   49 |     while(p[n] != n)
      |     ^~~~~
plan.cpp:51:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   51 |  return p[n];
      |  ^~~~~~
plan.cpp: In function 'int main()':
plan.cpp:133:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:134:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...