제출 #819972

#제출 시각아이디문제언어결과실행 시간메모리
819972I_Love_EliskaM_웜뱃 (IOI13_wombats)C++17
55 / 100
20064 ms190012 KiB
#include "wombats.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() #define pi pair<int,int> #define f first #define s second const int inf=1e9; const int N=10000; const int C=205; int opt[C][C]; int n,c; struct sgt { struct node { int empty=1; vector<vector<int>> v; node() { empty=1; } }; vector<node> t; int sz=1; sgt(int n) { while (sz<n) sz<<=1; t.assign(2*sz,node()); } node merge(node&a, node&b) { if (b.empty) return a; if (a.empty) return b; node n; n.empty=0; n.v.assign(c,vector<int>(c,inf)); forn(i,c) { forn(j,c) { if (a.v[i][j]+b.v[j][i] < n.v[i][i]) { n.v[i][i] = a.v[i][j]+b.v[j][i]; opt[i][i]=j; } } } for (int k=1; k<c; ++k) { for (int l=0; l+k<c; ++l) { int r = l+k; for (int m=opt[l][r-1]; m<=opt[l+1][r]; ++m) { if (a.v[l][m]+b.v[m][r] < n.v[l][r]) { n.v[l][r] = a.v[l][m]+b.v[m][r]; opt[l][r] = m; } } } for (int l=0; l+k<c; ++l) { int r = l+k; for (int m=opt[r-1][l]; m<=opt[r][l+1]; ++m) { if (a.v[r][m]+b.v[m][l] < n.v[r][l]) { n.v[r][l] = a.v[r][m]+b.v[m][l]; opt[r][l] = m; } } } } return n; } void upd(int v, int l, int r, int i) { if (r-l==1) return; int m=(l+r)>>1; if (i<m) upd(2*v+1,l,m,i); else upd(2*v+2,m,r,i); t[v]=merge(t[2*v+1],t[2*v+2]); } void set(int i, vector<vector<int>>&v) { t[sz-1+i].v=v; t[sz-1+i].empty=0; upd(0,0,sz,i); } }; const int K=10; sgt st(N/K); int d[K*C][C]; int h[N][C]; int v[N][C]; bitset<2*C> vis; void work(int i) { vector<vector<int>> t(c,vector<int>(c,1e9)); if (i>=n-1) return; for(int j=i; j<min(i+K,n-1); ++j) { forn(p,c) { vis.reset(); priority_queue<pi> q; q.push({0,p}); while (q.size()) { auto it=q.top(); q.pop(); int u=it.s, di=-it.f; if (vis[u]) continue; vis[u]=1; if (u<c) { if (u) q.push({-di-h[j][u-1],u-1}); if (u<c-1) q.push({-di-h[j][u],u+1}); q.push({-di-v[j][u],u+c}); } else { d[p+c*(j-i)][u-c]=di; if (u-c) q.push({-di-h[j+1][u-c-1],u-1}); if (u-c<c-1) q.push({-di-h[j+1][u-c],u+1}); } } } } auto f=t; auto s=f; forn(p,c) forn(q,c) s[p][q]=d[p][q]; for(int j=i+1; j<min(i+K,n-1); ++j) { forn(p,c) { forn(q,c) { if (s[p][q]+d[q+(j-i)*c][p] < f[p][p]) { f[p][p] = s[p][q]+d[q+(j-i)*c][p]; opt[p][p] = q; } } } for(int k=1; k<c; ++k) { for (int l=0; l+k<c; ++l) { int r=l+k; for (int m=opt[l][r-1]; m<=opt[l+1][r]; ++m) { if (s[l][m]+d[m+(j-i)*c][r] < f[l][r]) { f[l][r] = s[l][m]+d[m+(j-i)*c][r]; opt[l][r]=m; } } } } for(int k=1; k<c; ++k) { for (int l=0; l+k<c; ++l) { int r=l+k; for (int m=opt[r-1][l]; m<=opt[r][l+1]; ++m) { if (s[r][m]+d[m+(j-i)*c][l] < f[r][l]) { f[r][l] = s[r][m]+d[m+(j-i)*c][l]; opt[r][l]=m; } } } } s=f; f=t; } st.set(i/K,s); } void init(int _n, int _c, int _h[][200], int _v[][200]) { n=_n, c=_c; forn(i,n) forn(j,c-1) h[i][j]=_h[i][j]; forn(i,n-1) forn(j,c) v[i][j]=_v[i][j]; for (int i=0; i<n-1; i+=K) { work(i); } } void changeH(int i, int j, int w) { h[i][j]=w; work((i/K)*K); if ((i+1)/K*K != i/K*K) work((i+1)/K*K); if (i) if ((i-1)/K*K != i/K*K) work((i-1)/K*K); } void changeV(int i, int j, int w) { v[i][j]=w; work((i/K)*K); } int escape(int i, int j) { return st.t[0].v[i][j]; }

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#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...