oj.uz

Submission #1071018

# Submission time Handle Problem Language Result Execution time Memory
1071018 2024-08-23T00:28:04 Z 8pete8 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 150668 KB 
#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[300][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){
    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]);
}
struct seg{
    vector<vector<int>>v[1000];
    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=20;
    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);
}
//answer too quickly?? too much spare time?
//maybe try shifting weight on qry?
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

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:45:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 |     void build(int l,int r,int pos){
      |                                   ^
wombats.cpp:57:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |     void update(int l,int r,int qpos,int pos){
      |                                             ^
wombats.cpp:69:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   69 | void cal(int id){
      |                ^
wombats.cpp:90:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   90 | void init(int R, int C, int H[5000][200], int V[5000][200]){
      |                                                           ^
wombats.cpp:101:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  101 | void changeH(int P, int Q, int W){
      |                                 ^
wombats.cpp:106:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 | 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 53852 KB Output is correct
2 Correct 5 ms 53852 KB Output is correct
3 Correct 42 ms 56660 KB Output is correct
4 Correct 6 ms 53852 KB Output is correct
5 Correct 6 ms 53852 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6604 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 1 ms 8668 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 41 ms 10844 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 11304 KB Output is correct
2 Correct 264 ms 11568 KB Output is correct
3 Correct 229 ms 11308 KB Output is correct
4 Correct 219 ms 11312 KB Output is correct
5 Correct 262 ms 11304 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1333 ms 11352 KB Output is correct
10 Correct 1 ms 8640 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 57948 KB Output is correct
2 Correct 7 ms 58060 KB Output is correct
3 Correct 7 ms 57948 KB Output is correct
4 Correct 26 ms 59436 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 11096 KB Output is correct
2 Correct 262 ms 11100 KB Output is correct
3 Correct 231 ms 11308 KB Output is correct
4 Correct 219 ms 11308 KB Output is correct
5 Correct 261 ms 11100 KB Output is correct
6 Correct 9 ms 57944 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 7 ms 57948 KB Output is correct
9 Correct 31 ms 59732 KB Output is correct
10 Correct 6 ms 53852 KB Output is correct
11 Correct 6 ms 53892 KB Output is correct
12 Correct 44 ms 56660 KB Output is correct
13 Correct 6 ms 53852 KB Output is correct
14 Correct 6 ms 53912 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 2 ms 8540 KB Output is correct
25 Correct 41 ms 10936 KB Output is correct
26 Correct 1 ms 8536 KB Output is correct
27 Correct 1317 ms 11304 KB Output is correct
28 Correct 3609 ms 83648 KB Output is correct
29 Correct 3469 ms 71356 KB Output is correct
30 Correct 3569 ms 71152 KB Output is correct
31 Correct 3655 ms 85304 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 11100 KB Output is correct
2 Correct 261 ms 11288 KB Output is correct
3 Correct 229 ms 11100 KB Output is correct
4 Correct 238 ms 11352 KB Output is correct
5 Correct 268 ms 11100 KB Output is correct
6 Correct 8 ms 57944 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 8 ms 57944 KB Output is correct
9 Correct 30 ms 59476 KB Output is correct
10 Correct 7 ms 53848 KB Output is correct
11 Correct 5 ms 53852 KB Output is correct
12 Correct 45 ms 56548 KB Output is correct
13 Correct 6 ms 53848 KB Output is correct
14 Correct 6 ms 53844 KB Output is correct
15 Correct 2281 ms 150156 KB Output is correct
16 Execution timed out 20033 ms 150668 KB Time limit exceeded
17 Halted 0 ms 0 KB -