oj.uz

답안 #29707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29707 2017-07-20T11:13:53 Z osmanorhan 웜뱃 (IOI13_wombats) C++14
0 / 100
 363 ms 179968 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 R[5001][201];
int C[5001][201];
int opt[201][201];
void print( node t ) {
    printf("------- %d %d\n",t.l,t.r);
    for(int i=0;i<c;i++,printf("\n"))
        for(int j=0;j<c;j++) printf("%d ",t.go[i][j]);
}
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.l && !b.r ) return a;
    if( !a.l && !a.r ) 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]+R[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] );
    //printf("-------- %d\n",n);
    //print( t );
    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];

    //print( t );
        for(int i=0;i<c;i++) relax( k+1, t.go[i] );
    //print( t );
    //printf("----------- %d\n",k+1);
    }

}

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];

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

    for(int i=0;i*10<r;i++) {
        segment[i+n].l = i*10;
        segment[i+n].r = min( i*10+9, r-1 );
        calc( i+n );
    }
    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 / 10 + n;
    if( P%10 != 9 ) {
        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;
    for(int k=(P/10+n)>>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:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0;p<v.size();p++) {
                  ^

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 179964 KB Output is correct
2 Incorrect 299 ms 179968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 179496 KB Output is correct
2 Correct 0 ms 179496 KB Output is correct
3 Correct 0 ms 179492 KB Output is correct
4 Incorrect 0 ms 179968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 179968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 363 ms 179964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 76 ms 179964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 179964 KB Output isn't correct
2 Halted 0 ms 0 KB -