제출 #836091

#제출 시각아이디문제언어결과실행 시간메모리
836091definitelynotmee웜뱃 (IOI13_wombats)C++17
100 / 100
14912 ms187836 KiB
// #include "grader.c" #include"wombats.h" #include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define ff first #define ss second using namespace std; using ll = long long; using pii = pair<int,int>; template<typename T> using matrix = vector<vector<T>>; const int INF = 1e9; const int MAXN = 200; template<typename T> using mat = array<array<int,MAXN>,MAXN>; struct matriz{ mat<int> v; int n; matriz(int sz = 0, int val = INF){ n = sz; for(int i = 0; i < sz; i++){ fill(v[i].begin(), v[i].begin()+n, val); } } matriz operator*(matriz other){ matriz ret(n); auto solve =[&](int source, int l, int r, int optl, int optr, auto solve) -> void { if(r < l) return; int m = (l+r)>>1; int opt = optl; for (int i = optl+1; i <= optr; i++) opt = min(opt,i,[&](int a, int b){ return v[source][a]+other.v[a][m] < v[source][b]+other.v[b][m]; }); ret.v[source][m] = min(INF,v[source][opt]+other.v[opt][m]); solve(source,m+1,r,opt,optr,solve); solve(source,l,m-1,optl,opt,solve); }; for(int i = 0; i < n; i++) solve(i,0,n-1,0,n-1,solve); // for(int i = 0; i < n; i++){ // for(int j = 0; j < n; j++){ // for(int k = 0; k < n; k++){ // ret.v[i][j] = min(v[i][k]+other.v[k][j], ret.v[i][j]); // } // } // } return ret; } void swap(matriz& other){ v.swap(other.v); } }; int getmid(int l, int r){ return min(l+(1<<__lg(r-l+1))-1, r-(1<<__lg(r-l+1)-1)); } struct SegTree{ vector<matriz> tree; int sz, q; matriz val; SegTree(int n = 0, int m = 0){ sz = n; tree = vector<matriz>(2*n+2,matriz(m)); } void update(int id, int l, int r){ if(l > q || r < q) return; if(l == q && r == q){ tree[id] = val; return; } int e = id*2+1, d = id*2+2, m = getmid(l,r); update(e,l,m); update(d,m+1,r); tree[id] = tree[e]*tree[d]; } void makeupd(int id, matriz v){ val = v; q = id; update(0,0,sz-1); } }st; matriz pogmerge(matriz m1, matriz m2, vector<int> col){ int n = m1.n; matriz ret(n); auto solve =[&](int source, int l, int r, int optl, int optr, auto solve) -> void { if(r < l) return; int m = (l+r)>>1; int opt = optl; for (int i = optl+1; i <= optr; i++) opt = min(opt,i,[&](int a, int b){ return m1.v[source][a]+m2.v[a][m]+col[a] < m1.v[source][b]+m2.v[b][m]+col[b]; }); ret.v[source][m] = min(INF,m1.v[source][opt]+m2.v[opt][m]+col[opt]); solve(source,m+1,r,opt,optr,solve); solve(source,l,m-1,optl,opt,solve); }; for(int i = 0; i < n; i++) solve(i,0,n-1,0,n-1,solve); // for(int i = 0; i < n; i++){ // for(int j = 0; j < n; j++){ // for(int k = 0; k < n; k++){ // ret.v[i][j] = min(v[i][k]+other.v[k][j], ret.v[i][j]); // } // } // } return ret; } int n, m; const int len = 10; int bct; matrix<int> hor; matrix<int> ver; matriz build_in_row(int linha){ matriz ret(m,0); for(int j = 0; j < m; j++){ int cur = 0; for(int k = j; k < m-1; k++){ cur+=hor[linha][k]; ret.v[j][k+1] = ret.v[k+1][j] = cur; } } return ret; } matriz build_next(int linha, matriz& antes, matriz& depois){ matriz col(m); for(int i = 0; i < m; i++) col.v[i][i] = ver[linha][i]; return antes*col*depois; } void buildblock(int bid){ int l = bid*len, r = min((bid+1)*len,n-1); // cerr << bid << ' ' << l << ' ' << r << endl; matriz res = build_in_row(l); for(int i = 0; i < m; i++) res.v[i][i] = 0; for(int i = l; i < r; i++){ res = pogmerge(res,build_in_row(i+1),ver[i]); } st.makeupd(bid,res); // cerr << l << ' ' << r << ":\n"; // for(int i = 0; i < m; i++){ // for(int j = 0; j < m; j++){ // cerr << res.v[i][j] << ' '; // } // cerr << '\n'; // } } void init(int R, int C, int H[5000][200], int V[5000][200]) { // cerr << "ok" << endl; n = R; m = C; // cerr << n << ' ' << m << endl; hor = matrix<int>(n,vector<int>(m-1)); ver = matrix<int>(n-1,vector<int>(m)); // cerr << "ok" << endl; for(int i = 0; i < n; i++){ for(int j = 0; j < m-1; j++) hor[i][j] = H[i][j]; } for(int i = 0; i < n-1; i++){ for(int j = 0; j < m; j++){ ver[i][j] = V[i][j]; } } bct = (n-2+len)/len; st = SegTree(bct,m); for(int i = 0; i < bct; i++){ buildblock(i); } } void changeH(int P, int Q, int W) { // cerr << P << ' ' << Q << endl; hor[P][Q] = W; int bid = P/len; int lastbid = (P-1)/len; if(bid<bct) buildblock(bid); if(bid!=lastbid) buildblock(lastbid); } void changeV(int P, int Q, int W) { // cerr << P << ' ' << Q << endl; ver[P][Q] = W; int bid = P/len; buildblock(bid); } int escape(int V1, int V2) { // cerr << V1 << ' ' << V2 << endl; return st.tree[0].v[V1][V2]; }

컴파일 시 표준 에러 (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;
      |      ^~~
wombats.cpp: In function 'int getmid(int, int)':
wombats.cpp:71:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |     return min(l+(1<<__lg(r-l+1))-1, r-(1<<__lg(r-l+1)-1));
      |                                            ~~~~~~~~~~~^~
#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...