# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
951717 | 2024-03-22T11:37:09 Z | Baizho | Toll (BOI17_toll) | C++14 | 408 ms | 524288 KB |
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> // #pragma GCC optimize("Ofast,unroll-loops,fast-math") // #pragma GCC target("popcnt,avx") typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; #define sz size() #define ff first #define ss second #define all(a) a.begin(),a.end() #define pb push_back const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6 const ll MOD = 998244353; // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod const int N = ll(5e4)+100; const int M = ll(2e5) + 100; const long long inf = 5e18; //const long double eps = 1e-15L; ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; } ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;} void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); } int k, n, m, q, qa[N], qb[N], dis[N][3005], pos[N]; bitset<N> vis; vector<pair<int, int> > g[N]; vector<int> top; void dfs(int v) { vis[v] = 1; for(auto to : g[v]) { if(vis[to.ff]) continue; dfs(to.ff); } top.pb(v); } void Baizho() { cin>>k>>n>>m>>q; for(int i = 1; i <= m; i ++) { int a, b, t; cin>>a>>b>>t; g[a].pb({b, t}); } for(int i = 0; i < n; i ++) { if(!vis[i]) dfs(i); for(int j = 1; j <= q; j ++) dis[i][j] = 2e9; } for(int i = 1; i <= q; i ++) { cin>>qa[i]>>qb[i]; pos[qb[i]] = i; } for(auto v : top) { if(pos[v]) dis[v][pos[v]] = 0; for(auto to : g[v]) { for(int i = 1; i <= q; i ++) { if(dis[to.ff][i] != 2e9) dis[v][i] = min(dis[v][i], dis[to.ff][i] + to.ss); } } } for(int i = 1; i <= q; i ++) { if(dis[qa[i]][pos[qb[i]]] == 2e9) dis[qa[i]][pos[qb[i]]] = -1; cout<<dis[qa[i]][pos[qb[i]]]<<"\n"; } } signed main() { // Freopen("nondec"); ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); // precalc(); int ttt = 1; // cin>>ttt; for(int i=1; i<=ttt; i++) {Baizho(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 408 ms | 524288 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 293 ms | 524288 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 3 ms | 14940 KB | Output is correct |
7 | Correct | 5 ms | 14984 KB | Output is correct |
8 | Correct | 5 ms | 14940 KB | Output is correct |
9 | Correct | 3 ms | 14940 KB | Output is correct |
10 | Correct | 112 ms | 339716 KB | Output is correct |
11 | Correct | 113 ms | 340500 KB | Output is correct |
12 | Correct | 139 ms | 342824 KB | Output is correct |
13 | Correct | 145 ms | 343496 KB | Output is correct |
14 | Correct | 121 ms | 342220 KB | Output is correct |
15 | Correct | 77 ms | 251908 KB | Output is correct |
16 | Correct | 76 ms | 250456 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Correct | 1 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 3 ms | 14940 KB | Output is correct |
7 | Correct | 5 ms | 14984 KB | Output is correct |
8 | Correct | 5 ms | 14940 KB | Output is correct |
9 | Correct | 3 ms | 14940 KB | Output is correct |
10 | Correct | 112 ms | 339716 KB | Output is correct |
11 | Correct | 113 ms | 340500 KB | Output is correct |
12 | Correct | 139 ms | 342824 KB | Output is correct |
13 | Correct | 145 ms | 343496 KB | Output is correct |
14 | Correct | 121 ms | 342220 KB | Output is correct |
15 | Correct | 77 ms | 251908 KB | Output is correct |
16 | Correct | 76 ms | 250456 KB | Output is correct |
17 | Runtime error | 216 ms | 524288 KB | Execution killed with signal 9 |
18 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 408 ms | 524288 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |