Submission #760424

#TimeUsernameProblemLanguageResultExecution timeMemory
760424shadow_samiToll (BOI17_toll)C++17
7 / 100
3031 ms7372 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; typedef long long ll; typedef vector<ll> vi; typedef vector<vector<ll>> vvi; typedef pair<ll,ll> pi; #define ff first #define ss second #define fip(a,b) for(ll i = a ; i < b ; i++) #define fjp(a,b) for(ll j = a ; j < b ; j++) #define fp(x,a,b) for(ll x = a ; x < b ; x++) #define fin(a,b) for(ll i = a : i >= b; i--) #define fjn(a,b) for(ll j = a : j >= b; j--) #define fn(x,a,b) for(ll x = a ; x >= b ; x--); #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> #define total_one(a) __builtin_popcount(a) #define front_zero(a) __builtin_clzll(a) #define back_zero(a) __builtin_ctzll(a) #define fx(a) for(auto x : a) #define nli "\n" #if ONLINE_JUDGE #define debug(x) cerr<< #x <<" "<< printn(n) << nli; #else #define debug(x) #endif void printn(ll a){ cerr<<a<<" ";} void printn(int a){ cerr<<a<<" ";} template <class T,class V> void _printn(pair<T,V> a){ cerr<<"( "<<a.ff<<" , "<<a.ss<<" ) "<<nli;} template <class T> void _printn(vector<T> a){ cerr<<"[ "; for(auto x : a){ _printn(a); cerr<<nli; } cerr<<"]"<<nli; return; } const ll mx = 1e5+5; ll n,m,k,q,tp,tp2,res,sum,tptp,cnt,ans; bool f = false; ll timer = 0; vector<pi> adj[mx]; ll conn[mx]; ll dis[mx]; void dfs(ll u){ fx(adj[u]){ dis[x.ff] = dis[u] + x.ss; conn[x.ff] = conn[u]; dfs(x.ff); } return; } int sr,de; 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 cin>>k>>n>>m>>tptp; fip(0,m){ cin>>sr>>de>>tp; adj[sr].push_back({de,tp}); } fip(0,n+2) dis[i] = 1e18,conn[i] = -1; fip(0,n+1){ if(conn[i]==-1){ if((int)adj[i].size() == 0) continue; dis[i] = 0; conn[i] = timer; timer++; dfs(i); } } // fip(0,n) // cout<<conn[i]<<" "; // cout<<nli; while(tptp--){ cin>>sr>>de; if(dis[de] > 1e9 || dis[sr] > 1e9 || sr > de || conn[sr] != conn[de]){ cout<<-1<<nli; continue; } cout<<dis[de]-dis[sr]<<nli; } cerr << "time elapsed : " <<setprecision(6)<< clock() * 1000.00 / CLOCKS_PER_SEC << " ms"<<nli; return 0; }
#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...