제출 #720894

#제출 시각아이디문제언어결과실행 시간메모리
720894urosk던전 (IOI21_dungeons)C++17
11 / 100
7107 ms63708 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define here cerr<<"===========================================\n" #define dbg(x) cerr<<#x<<": "<<x<<endl; #define ll long long #define pb push_back using namespace std; #define maxn 400005 #define lg 50 ll n; vector<ll> g[maxn]; vector<ll> v[maxn]; ll a[maxn],b[maxn]; bool sub3 = 1; bool sub1 = 1; ll dis[maxn]; ll deg[maxn]; ll st[maxn][lg]; ll sum[maxn][lg]; ll cyc[maxn]; ll val[maxn]; ll len[maxn]; bool vis[maxn]; ll tsz = 0; void dfs(ll u,ll p){ for(ll s : v[u]){ if(s==p) continue; dis[s] = dis[u] + 1; dfs(s,u); } } void dfs2(ll u,ll p){ vis[u] = 1; cyc[u] = tsz; val[tsz]+=b[u]; len[tsz]++; for(ll s : g[u]){ if(vis[s]) continue; dfs2(s,u); } } bool sub2 = 0; void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { n = N; for(ll i = 1;i<=n;i++) a[i] = s[i-1]; for(ll i = 1;i<=n;i++) b[i] = p[i-1]; for(ll i = 1;i<n;i++) sub3&=(a[i]==a[i+1]); for(ll i = 1;i<=n;i++){ if(sub3) v[w[i-1]+1].pb(i); else v[i].pb(w[i-1]+1); } for(ll i = 1;i<=n;i++) g[i].pb(l[i-1]+1); if(sub3){ dfs(n+1,n+1); for(ll i = 1;i<=n;i++){ for(ll j : g[i]) deg[j]++; } queue<ll> q; for(ll i = 1;i<=n+1;i++) if(!deg[i]) q.push(i); for(ll i = 1;i<=n;i++) cyc[i] = 1; while(q.size()){ ll u = q.front(); q.pop(); cyc[u] = 0; for(ll s : g[u]){ deg[s]--; if(!deg[s]) q.push(s); } } for(ll i = 1;i<=n;i++){ st[i][0] = g[i][0]; sum[i][0] = b[i]; } st[n+1][0] = n+1; for(ll j = 1;j<lg;j++){ for(ll i = 1;i<=n+1;i++){ st[i][j] = st[st[i][j-1]][j-1]; sum[i][j] = sum[i][j-1] + sum[st[i][j-1]][j-1]; } } for(ll i = 1;i<=n;i++){ if(!cyc[i]) continue; if(vis[i]) continue; ++tsz; dfs2(i,i); } } return; } long long simulate(int x, int z) { if(sub2) return 0; x++; if(!sub3){ while(x!=n+1){ if(z>=a[x]){ z+=a[x]; x = v[x][0]; }else{ z+=b[x]; x = g[x][0]; } } return z; } ll s = a[1]; if(z>=s) return z + s*dis[x]; for(ll j = lg-1;j>=0;j--){ if(sum[x][j]+z<s){ z+=sum[x][j]; x = st[x][j]; } } if(x==n+1) return z; return z + b[x] + s*dis[g[x][0]]; z+=b[x]; x = g[x][0]; if(x==n+1) return z; z+=((s-z)/val[cyc[x]])*val[cyc[x]]; if(z==s) return s + s*dis[x]; for(ll j = lg-1;j>=0;j--){ if(sum[x][j]>val[cyc[x]]) continue; if(z+sum[x][j]<s) x = st[x][j]; } z+=b[x]; x = g[x][0]; return z + s*dis[x]; } /** 3 2 2 6 9 3 1 2 2 2 3 1 0 1 0 1 2 3 3 2 9 9 9 3 1 2 2 2 3 1 0 1 0 1 2 3 **/
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...