oj.uz

Submission #1070508

# Submission time Handle Problem Language Result Execution time Memory
1070508 2024-08-22T14:51:08 Z 8pete8 Wombats (IOI13_wombats) C++17
76 / 100
 20000 ms 67252 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[101][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){
    vector<vector<int>>ans(m,vector<int>(m,inf));
    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]);
    //return ans;
}
struct seg{
    vector<vector<int>>v[400];
    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=50;
    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);
}
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:47:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 |     void build(int l,int r,int pos){
      |                                   ^
wombats.cpp:59:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 |     void update(int l,int r,int qpos,int pos){
      |                                             ^
wombats.cpp:71:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   71 | void cal(int id){
      |                ^
wombats.cpp:92:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   92 | void init(int R, int C, int H[5000][200], int V[5000][200]){
      |                                                           ^
wombats.cpp:103:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  103 | void changeH(int P, int Q, int W){
      |                                 ^
wombats.cpp:108:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | 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 4 ms 27224 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 41 ms 28800 KB Output is correct
4 Correct 4 ms 27224 KB Output is correct
5 Correct 4 ms 27220 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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8536 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 42 ms 9420 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 179 ms 8796 KB Output is correct
2 Correct 167 ms 8796 KB Output is correct
3 Correct 170 ms 8796 KB Output is correct
4 Correct 177 ms 8792 KB Output is correct
5 Correct 177 ms 8796 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
9 Correct 854 ms 8984 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31320 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 26 ms 32092 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 8792 KB Output is correct
2 Correct 170 ms 8792 KB Output is correct
3 Correct 169 ms 8964 KB Output is correct
4 Correct 171 ms 8964 KB Output is correct
5 Correct 174 ms 8956 KB Output is correct
6 Correct 5 ms 31324 KB Output is correct
7 Correct 5 ms 31332 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 25 ms 32052 KB Output is correct
10 Correct 4 ms 27224 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 43 ms 28884 KB Output is correct
13 Correct 4 ms 27224 KB Output is correct
14 Correct 4 ms 27224 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 6744 KB Output is correct
18 Correct 2 ms 8536 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 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 42 ms 9528 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 847 ms 8964 KB Output is correct
28 Correct 3245 ms 40752 KB Output is correct
29 Correct 3182 ms 38740 KB Output is correct
30 Correct 3166 ms 38736 KB Output is correct
31 Correct 3383 ms 41796 KB Output is correct
32 Correct 1 ms 8792 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 8796 KB Output is correct
2 Correct 168 ms 8792 KB Output is correct
3 Correct 170 ms 8792 KB Output is correct
4 Correct 172 ms 8792 KB Output is correct
5 Correct 173 ms 8796 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 5 ms 31324 KB Output is correct
9 Correct 24 ms 32000 KB Output is correct
10 Correct 4 ms 27228 KB Output is correct
11 Correct 3 ms 27228 KB Output is correct
12 Correct 48 ms 28688 KB Output is correct
13 Correct 3 ms 27228 KB Output is correct
14 Correct 4 ms 27228 KB Output is correct
15 Correct 1240 ms 65616 KB Output is correct
16 Execution timed out 20044 ms 67252 KB Time limit exceeded
17 Halted 0 ms 0 KB -