oj.uz

Submission #29784

# Submission time Handle Problem Language Result Execution time Memory
29784 2017-07-20T15:20:01 Z osmanorhan Wombats (IOI13_wombats) C++14
28 / 100
 799 ms 180184 KB 
#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 = 1;
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

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 179496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 179968 KB Output is correct
2 Correct 0 ms 179972 KB Output is correct
3 Correct 0 ms 179968 KB Output is correct
4 Correct 3 ms 179972 KB Output is correct
5 Correct 0 ms 179972 KB Output is correct
6 Correct 3 ms 179972 KB Output is correct
7 Correct 3 ms 179976 KB Output is correct
8 Correct 3 ms 179968 KB Output is correct
9 Correct 3 ms 179968 KB Output is correct
10 Correct 0 ms 179968 KB Output is correct
11 Correct 73 ms 179968 KB Output is correct
12 Correct 3 ms 179972 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 180180 KB Output is correct
2 Correct 169 ms 180176 KB Output is correct
3 Correct 219 ms 180180 KB Output is correct
4 Correct 219 ms 180184 KB Output is correct
5 Correct 223 ms 180180 KB Output is correct
6 Correct 0 ms 179972 KB Output is correct
7 Correct 0 ms 179968 KB Output is correct
8 Correct 0 ms 179972 KB Output is correct
9 Correct 799 ms 180180 KB Output is correct
10 Correct 0 ms 179972 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 179496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 180180 KB Output is correct
2 Correct 176 ms 180176 KB Output is correct
3 Correct 243 ms 180180 KB Output is correct
4 Correct 226 ms 180180 KB Output is correct
5 Correct 213 ms 180176 KB Output is correct
6 Runtime error 6 ms 179492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 180176 KB Output is correct
2 Correct 173 ms 180176 KB Output is correct
3 Correct 209 ms 180180 KB Output is correct
4 Correct 229 ms 180180 KB Output is correct
5 Correct 189 ms 180180 KB Output is correct
6 Runtime error 3 ms 179496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -