Submission #1258207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258207		Szymon_Pilipczuk	Wombats (IOI13_wombats)	C++20	76 / 100	20087 ms	181620 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int h,w;
int calc[1024][200][200];
int grid[5000][200][3];
void comb(int v)
{
    vector<vector<int>> opt(w);
    rep(i,w)
    {
        opt[i].resize(w);
    }
    rep(j,w)
    {
        for(int i = w-1;i>=0;i--)
        {
            int l = 0;
            int r = w-1;
            if(i != w-1)
            {
                r = opt[i+1][j];
            }
            if(j != 0)
            {
                l = opt[i][j-1];
            }
            int mn = inf;
            for(int q = l;q<=r;q++)
            {
                if(calc[v*2][i][q] + calc[v*2+1][q][j] < mn || (i == q && calc[v*2][i][q] + calc[v*2+1][q][j] == mn))
                {
                    mn = calc[v*2][i][q] + calc[v*2+1][q][j];
                    opt[i][j] = q;
                }
            }
            calc[v][i][j] = mn;
        }
    }
}
int mod;
int ize;
priority_queue<pair<int,pair<int,int>>> pq;
int dis[11][200];
void ds(int c,int a,int b)
{
    if(b != w-1 && dis[a-mod][b+1] > c + grid[a][b][0])
    {
        pq.push({(c+grid[a][b][0])*-1,{a,b+1}});
        dis[a-mod][b+1] = c + grid[a][b][0];
    }
    if(a- mod != ize-1 && dis[a-mod+1][b] > c + grid[a][b][1])
    {
        pq.push({(c+grid[a][b][1])*-1,{a+1,b}});
        dis[a-mod+1][b] = c + grid[a][b][1];

    }
    if(b != 0 && dis[a-mod][b-1] > c + grid[a][b][2])
    {
        pq.push({(c+grid[a][b][2])*-1,{a,b-1}});
        dis[a-mod][b-1] = c + grid[a][b][2];
    }
}
void dk(int l)
{
    l *= 10;
    if(l >= h-1)
    {
        rep(i,w)
        {
            rep(j,w)
            {
                calc[l/10+512][i][j] = inf;
            }
            calc[l/10+512][i][i] = 0;
        }
        return;
    }
    ize = min(11,h-l);
    mod = l;
    rep(i,w)
    {
        rep(j,ize)
        {
            rep(q,w)
            {
                dis[j][q] = inf;
            }
        }
        dis[0][i] = 0;
        pq.push({0,{mod,i}});
        while(!pq.empty())
        {
            pair<int,pair<int,int>> c = pq.top();
            pq.pop();
            ds(c.st*-1,c.nd.st,c.nd.nd);
        }
        rep(j,w)
        {
            calc[l/10+512][i][j] = dis[ize-1][j];
        }
    }
}
void ch(int l)
{
    dk(l);
    l+=512;
    l/=2;
    while(l > 0)
    {
        comb(l);
        l/=2;
    }
}
void init(int r,int c,int H[5000][200],int V[5000][200])
{
    h = r;
    w = c;
    rep(i,h)
    {
        rep(j,w-1)
        {
            grid[i][j][0] = H[i][j];
            grid[i][j+1][2] = H[i][j];
        }
    }
    rep(i,h-1)
    {
        rep(j,w)
        {
            grid[i][j][1] = V[i][j];
        }
    }
    rep(i,512)
    {
        dk(i);
    }
    for(int j = 511;j>0;j--)
    {
        comb(j);
    }
}
void changeH(int p,int q,int w)
{
    grid[p][q][0] = w;
    grid[p][q+1][2] = w;
    ch(p/10);
    if(p%10 == 0 && p > 0)
    {
        ch(p/10-1);
    }
}
void changeV(int p,int q,int w)
{
    grid[p][q][1] = w;
    ch(p/10);
}
int escape(int v1,int v2)
{
    return calc[1][v1][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