Submission #29785

#	Time	Username	Problem	Language	Result	Execution time	Memory
29785		osmanorhan	Wombats (IOI13_wombats)	C++14	100 / 100	7259 ms	180568 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define umax( x, y ) x = max( x, y )
#define umin( x, y ) x = min( x, y )

using namespace std;

const int maxn = 100000;
const int maxR = 5020;
const int maxC = 220;

typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

struct node {
    int go[201][201];
    int l, r;
};

node segment[1<<10];
vector<ii> v;
int n, c, r;
int sz = 10;
int R[5001][201];
int C[5001][201];
int opt[201][201];

bool comp( const ii &a, const ii &b ) {
    return a.se-a.fi < b.se-b.fi;
}

node merge( node a, node b ) {
    if( b.r == -1 ) return a;
    if( a.r == -1 ) return b;

    node t;
    t.l = a.l;
    t.r = b.r;
    for(int p=0;p<v.size();p++) {
        int x = v[p].fi;
        int y = v[p].se;
        opt[x][y] = 0;
        int val = 1e9;
        int beg = 0, en = c-1;
        if( x+1 < c ) umin( en, opt[x+1][y] );
        if( y > 0 ) umax( beg, opt[x][y-1] );
        while( beg <= en ) {
            int h = a.go[x][beg]+C[a.r][beg]+b.go[beg][y];
            if( h < val ) {
                val = h;
                opt[x][y] = beg;
            }
            beg++;
        }
        t.go[x][y] = val;
    }
    return t;
}

void relax( int x, int ar[] ) {
    for(int i=c-2;i>=0;i--)
        umin( ar[i], ar[i+1]+R[x][i] );
    for(int i=1;i<c;i++)
        umin( ar[i], ar[i-1]+R[x][i-1] );
}

void calc( int n ) {
    node &t = segment[n];
    for(int i=0;i<c;i++)
        for(int j=0;j<c;j++)
            t.go[i][j] = (i==j)? 0:1e9;

    for(int i=0;i<c;i++) relax( t.l, t.go[i] );
    for(int k=t.l;k<t.r;k++) {

        for(int i=0;i<c;i++)
            for(int j=0;j<c;j++) t.go[i][j] += C[k][j];

        for(int i=0;i<c;i++) relax( k+1, t.go[i] );
    }

}

void init(int rr, int cc, int RR[5000][200], int CC[5000][200]) {

    r = rr;
    c = cc;
    for(int i=0;i<r;i++)
        for(int j=0;j<c-1;j++)
            R[i][j] = RR[i][j];
    for(int i=0;i<r-1;i++)
        for(int j=0;j<c;j++)
            C[i][j] = CC[i][j];

    for(int i=0;i<c;i++)
    for(int j=0;j<c;j++) v.pb( ii( i, j ) );
    sort( v.begin(), v.end(), comp );

    n = 1;
    while( n < (r-1)/sz+1 ) n <<= 1;

    for(int i=0;i<n;i++) {
        if( i*sz < r ) {
            segment[i+n].l = i*sz;
            segment[i+n].r = min( i*sz+sz-1, r-1 );
            calc( i+n );
        } else {
            segment[i+n].r = -1;
        }
    }
    for(int i=n-1;i>0;i--)
        segment[i] = merge( segment[i+i], segment[i+i+1] );
}

void changeH(int P, int Q, int W) {
    R[P][Q] = W;
    int k = (P/sz+n);
    calc( k );
    for(k>>=1;k;k>>=1) segment[k] = merge( segment[k+k], segment[k+k+1] );

}

void changeV(int P, int Q, int W) {
    C[P][Q] = W;
    int k = P / sz + n;
    if( P%sz != sz-1 ) {
        calc( k );
    }
    for(k>>=1;k;k>>=1)
        segment[k] = merge( segment[k+k], segment[k+k+1] );
}

int escape(int V1, int V2) {
    return segment[1].go[V1][V2];
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^
wombats.cpp: In function 'node merge(node, node)':
wombats.cpp:43:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0;p<v.size();p++) {
                  ^

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