Submission #757106

#TimeUsernameProblemLanguageResultExecution timeMemory
757106shadow_samiCrocodile's Underground City (IOI11_crocodile)C++17
100 / 100
552 ms94904 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long int ll; typedef vector<ll> vi; typedef vector<vector<ll>> vvi; typedef pair<ll,ll> pi; typedef map<ll,ll> mi; typedef long double ld; typedef vector<ld> vd; typedef vector<vector<ld>> vvd; typedef pair<ld,ld> pd; #define ff first #define ss second #define srt(a) sort(a.begin(),a.end()); #define fip(k, n) for (ll i = k; i < n; i++) #define fjp(k, n) for (ll j = k; j < n; j++) #define fin(k, n) for (ll i = k; i >= n; i--) #define fjn(k, n) for (ll j = k; j >= n; j--) #define fp(k, n, m) for (ll k = n; k < m; k++) #define fn(k, n, m) for (ll k = n; k >= m; k--) #define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update> #define totalOne(n) __builtin_popcount(n) #define backZero(n) __builtin_ctzll(n) #define frontZero(n) __builtin_clzll(n) #define fx(k) for ( auto x : k ) #define test ll t;cin >> t;while (t--) #define nli "\n" // ==========================(debug)============================================================================================== // #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" "; _printn(x); cerr << nli; #else #define debug(x) #endif void _printn(ll x){ cerr<<x<<" "; } void _printn(int x){ cerr<<x<<" "; } void _printn(ld x){ cerr<<x<<" "; } void _printn(double x){ cerr<<x<<" "; } void _printn(string x){ cerr<<x<<" "; } void _printn(char x){ cerr<<x<<" "; } void _printn(bool x){ cerr<<x<<" "; } template<class T,class V>void _printn(pair<T,V> vv); template<class T> void _printn(vector<T> vv); template<class T> void _printn(set<T> vv); template<class T,class V> void _printn(map<T,V> vv); template<class T> void _printn(multiset<T> vv); template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";} template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; }; template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; }; template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; }; template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; }; // ==========================(debug)============================================================================================== // ll n,m,tp,tp2,res,cnt,sum,tptp,ans; const ll mx = 2e5+5; const ll mod = 1e9+7; // ==========================(MOD)=============================================================================================== // ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; } ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; } ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; } ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; } ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; } // ==========================(MOD)=============================================================================================== // bool f = false; typedef struct edge { ll wet,des,tt,from; void init(ll a,ll b,ll c,ll d){ wet = a; des = b; tt = c; from = d; return; } void deb(){ cerr<<wet<<" "<<des<<" "<<tt<<" "<<from<<nli; return; } }ed; ed ee; class cmp{ public: bool operator()(ed a,ed b){ return a.wet > b.wet; } }; vector<pi> adj[mx]; ll dis[mx][2],k; ll to[mx][2]; bool mark[mx]; priority_queue<ed,vector<ed>,cmp> pq; bool vis[mx]; void dfs(ll u){ vis[u] = 1; // debug(u); fx(adj[u]){ if(vis[x.ff]) continue; if(to[u][1] == x.ff){ ans += x.ss; dfs(x.ff); } } } int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){ n = N; m = M; fip(0,m){ adj[R[i][0]].push_back({R[i][1],L[i]}); adj[R[i][1]].push_back({R[i][0],L[i]}); } // fip(0,n){ // debug(adj[i]); // } fip(0,n+2){ dis[i][0] = dis[i][1] = 1e18; to[i][0] = to[i][1] = -100; } k = K; fip(0,k){ tp = P[i]; mark[tp] = 1; dis[P[i]][1] = dis[P[i]][0] = 0; ee.init(0,tp,0,-100); pq.push(ee); } while(pq.size()){ auto it = pq.top(); pq.pop(); // it.deb(); if(dis[it.des][it.tt] != it.wet){ continue; } to[it.des][it.tt] = it.from; fx(adj[it.des]){ if(mark[x.ff]) continue; if(dis[x.ff][0] > dis[it.des][it.tt] + x.ss){ if(dis[x.ff][1] > dis[x.ff][0] && dis[x.ff][0] != 1e18){ dis[x.ff][1] = dis[x.ff][0]; ee.init(dis[x.ff][0],x.ff,1,to[x.ff][0]); pq.push(ee); } dis[x.ff][0] = dis[it.des][it.tt] + x.ss; to[x.ff][0] = it.des; } else if(dis[x.ff][1] > dis[it.des][it.tt] + x.ss){ ee.init(dis[it.des][it.tt] + x.ss,x.ff,1,it.des); pq.push(ee); dis[x.ff][1] = dis[it.des][it.tt] + x.ss; to[x.ff][1] = it.des; } } } // debug((int)pq.size()); // fip(0,n) // cout<<to[i][0]<<" "<<to[i][1]<<nli; // cout<<nli; // fip(0,n) // cout<<dis[i][0]<<" "<<dis[i][1]<<nli; // fip(0,n+2) // vis[i] = 0; dfs(0); return ans; } // int main(){ // ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // #ifndef ONLINE_JUDGE // freopen("input1.txt", "r", stdin); // freopen("output1.txt", "w", stdout); // freopen("error1.txt", "w", stderr); // #endif // ONLINE_JUDGE // int N,M,K; // cin>>N>>M>>K; // int R[M][2]; // int L[M]; // int P[K]; // fip(0,M){ // cin>>R[i][0]>>R[i][1]; // cin>>L[i]; // } // fip(0,K) // cin>>P[i]; // cout<<travel_plan(N,M,R,L,K,P)<<nli; // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n"; // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...