Submission #1070508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070508		8pete8	Wombats (IOI13_wombats)	C++17	76 / 100	20044 ms	67252 KiB

wombats

#include "wombats.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
const int inf=1e9;
int dist[101][202][202],costv[5005][202],costh[5005][200];
int n,m;
int pref[202],root,bound;
int ans[202][202],what[202][202];
void mul(vector<vector<int>>a,vector<vector<int>>b){
    vector<vector<int>>ans(m,vector<int>(m,inf));
    for(int i=0;i<m;i++)for(int j=0;j<m;j++)what[i][j]=inf;
    for(int i=0;i<m;i++)for(int j=0;j<m;j++)for(int k=0;k<m;k++)what[i][j]=min(what[i][j],a[i][k]+b[k][j]);
    //return ans;
}
struct seg{
    vector<vector<int>>v[400];
    void build(int l,int r,int pos){
        v[pos].resize(m,vector<int>(m));
        int mid=l+(r-l)/2;
        if(l==r){
            for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j];
            return;
        }
        build(l,mid,pos*2);
        build(mid+1,r,pos*2+1);
        mul(v[pos*2],v[pos*2+1]);
        for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j];
    }
    void update(int l,int r,int qpos,int pos){
        int mid=l+(r-l)/2;
        if(l==r){
            for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j];
            return;
        }
        if(qpos<=mid)update(l,mid,qpos,pos*2);
        else update(mid+1,r,qpos,pos*2+1);
        mul(v[pos*2],v[pos*2+1]);
        for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j];
    }
}t;
void cal(int id){
    for(int st=0;st<m;st++)for(int go=0;go<m;go++){
        if(st!=go)dist[id][st][go]=inf;
        else dist[id][st][go]=0;
    }
    for(int r=(id*root);r<min(n,(id*root)+root);r++)for(int st=0;st<m;st++){
        int mncost=inf,add=0;
        for(int go=0;go<m;go++){
            mncost=min(mncost,dist[id][st][go]-add);
            pref[go]=mncost+add;
            add+=costh[r][go];
        }
        mncost=inf,add=0;
        for(int go=m-1;go>=0;go--){
            mncost=min(mncost,dist[id][st][go]-add);
            dist[id][st][go]=min(pref[go],mncost+add);
            if(r!=n-1)dist[id][st][go]+=costv[r][go];
            if(go)add+=costh[r][go-1];
        }
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
    n=R,m=C;
    //root=sqrt(n);
    root=50;
    bound=((n-1)/root);
    for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)costh[i][j]=H[i][j];
    for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)costv[i][j]=V[i][j];
    for(int i=0;i<=bound;i++)cal(i);
    t.build(0,bound,1);
}
//500x200x200(blocksize+log(bound))
void changeH(int P, int Q, int W){
    costh[P][Q]=W;
    cal(P/root);
    t.update(0,bound,P/root,1);
}
void changeV(int P, int Q, int W){
    costv[P][Q]=W;
    cal(P/root);
    t.update(0,bound,P/root,1);
}
int escape(int V1, int V2){
    return t.v[1][V1][V2];
}
//70x200x200x500
/*
we can compute [start][at][row] 
=200x200x5000
for each update
how to improve?

use segtree? and matrix [from][go] 200x200
too much memory?

do sqrt decomp instead? trading time for space
split block 

what if we combine both sqrt and segtree 'o'?
we can do qry in
*/

Compilation message (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:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
wombats.cpp:39:51: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void mul(vector<vector<int>>a,vector<vector<int>>b){
      |                                                   ^
wombats.cpp:47:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 |     void build(int l,int r,int pos){
      |                                   ^
wombats.cpp:59:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 |     void update(int l,int r,int qpos,int pos){
      |                                             ^
wombats.cpp:71:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   71 | void cal(int id){
      |                ^
wombats.cpp:92:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   92 | void init(int R, int C, int H[5000][200], int V[5000][200]){
      |                                                           ^
wombats.cpp:103:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  103 | void changeH(int P, int Q, int W){
      |                                 ^
wombats.cpp:108:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | void changeV(int P, int Q, int W){
      |                                 ^
wombats.cpp:113:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  113 | int escape(int V1, int V2){
      |                          ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24