Submission #1109619

#TimeUsernameProblemLanguageResultExecution timeMemory
1109619vjudge1Toll (BOI17_toll)C++17
100 / 100
2847 ms7352 KiB
#include <bits/stdc++.h> /* #pragma GCC optimize ("O2") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("Ofast") #pragma GCC target ("avx2") */ using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #define F first #define S second #define pb push_back #define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) #define md(a) ((a%mod+mod)%mod) #define all(a) a.begin(), a.end() #define MP make_pair #define lc id<<1 #define rc lc|1 #define mid (l+r)/2 #define kill(a) cout << a << "\n", exit(0) typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll; typedef long double ld; typedef vector<vector<ll>> matrix; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn=5e4+10, INF=1e9+10, LOG=22, sq=65; ll poww(ll a, ll b, ll mod) { if (b == 0) return 1; return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod; } int n, m, k, o, f[maxn], l[maxn], dis[maxn]; vector<pair<pii, int>> E; map<pii, int> mp; int solve(int a, int b) { if(a==b) return 0; if(a>b || !f[a] || !l[b]) return -1; if(mp[{a, b}]!=0) return mp[{a, b}]; fill(dis+a, dis+b+1, INF); vector<int> s; dis[a]=0; for(int i=f[a];i<=min(m, l[b]);i++) { auto t=E[i-1]; int v=t.F.F, u=t.F.S, w=t.S; if(dis[v]+w<dis[u]) dis[u]=dis[v]+w; // s.pb(u); } // for(int i:s) mp[{a, i}]=dis[i]; mp[{a, b}]=dis[b]; return mp[{a, b}]; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>k>>n>>m>>o; for(int i=1;i<=m;i++) { int v, u, w; cin>>v>>u>>w; E.pb({{v, u}, w}); } fill(f, f+maxn, 0); fill(l, l+maxn, 0); int cur=1; sort(all(E)); for(auto t:E) { int v=t.F.F, u=t.F.S; if(f[v]==0) f[v]=cur; l[u]=cur; cur++; } while(o--) { int a, b; cin>>a>>b; int ans=solve(a, b); if(ans<INF) cout<<ans<<"\n"; else cout<<-1<<"\n"; } 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...