oj.uz

Submission #805574

# Submission time Handle Problem Language Result Execution time Memory
805574 2023-08-03T17:58:52 Z YassirSalama Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 20728 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXR=101;
const int MAXC=101;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
vector<set<pair<int,int>>> v(MAXR*MAXC);
map<pair<int,int>,int> mp;
int r,c;
int h[5000][200];
int vv[5000][200];
bool visited[MAXR*MAXC];
const ll INF=1e18;
vector<vector<ll>> dist2(MAXC,vector<ll>(MAXC));
vector<ll> dijkstra(ll node){
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
    memset(visited,false,sizeof(visited));
    vector<ll> dist(MAXR*MAXC,INF);
    dist[node]=0;
    q.push({0LL,node});
    while(!q.empty()){
        pair<ll,ll> p=q.top();
        q.pop();
        if(visited[p.S]) continue;
        visited[p.S]=true;
        for(auto x:v[p.S]){
            // dbg(dist[p.S],p.S,x.F,dist[x.F]);
            if(dist[x.F]>dist[p.S]+x.S){
                dist[x.F]=dist[p.S]+x.S;
                q.push({dist[x.F],x.F});
            }
        }
    }
    // OVL(dist," ")
    return dist;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    int a=0;
    r=R,c=C;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            h[i][j]=H[i][j];
            mp[{i,j}]=a;
            if(j==C-1) continue;
            v[a].insert({a+1,H[i][j]});
            v[a+1].insert({a,H[i][j]});
            // cout<<H[i][j]<<" ";
            a++;
        }a++;
    }
    a=0;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            vv[i][j]=V[i][j];
            v[a].insert({a+C,V[i][j]});
            a++;
        }
    }
    for(int i=0;i<MAXC;i++) {
        for(int j=0;j<MAXC;j++) dist2[i][j]=INF;
    }
    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=c*(r-1);j<c*r;j++){
            dist2[i][j-c*(r-1)]=min(dist2[i][j-c*(r-1)],dist[j]);
        }
    }
}

void changeH(int P, int Q, int W) {
    int ind=mp[{P,Q}];
    v[ind].erase({ind+1,h[P][Q]});
    v[ind+1].erase({ind,h[P][Q]});
    h[P][Q]=W;
    v[ind].insert({ind+1,h[P][Q]});
    v[ind+1].insert({ind,h[P][Q]});
    for(int i=0;i<MAXC;i++) {
        for(int j=0;j<MAXC;j++) dist2[i][j]=INF;
    }

    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=c*(r-1);j<c*r;j++){
            dist2[i][j-c*(r-1)]=min(dist2[i][j-c*(r-1)],dist[j]);
        }
    }

}

void changeV(int P, int Q, int W) {
    int ind=mp[{P,Q}];
    v[ind].erase({ind+c,vv[P][Q]});
    vv[P][Q]=W;
    v[ind].insert({ind+c,vv[P][Q]});
    for(int i=0;i<MAXC;i++) {
        for(int j=0;j<MAXC;j++) dist2[i][j]=INF;
    }
    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=c*(r-1);j<c*r;j++){
            dist2[i][j-c*(r-1)]=min(dist2[i][j-c*(r-1)],dist[j]);
        }
    }

}

int escape(int V1, int V2) {
    priority_queue<pair<int,int>> q;
    int ind=mp[{0,V1}];
    int ind2=mp[{r-1,V2}];
    return dist2[ind][ind2-c*(r-1)];
}


#ifdef IOI

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

static int H[5000][200];
static int V[5000][200];

int main() {
    int R, C, E, P, Q, W, V1, V2, event, i, j;
    int res;

    FILE *f = fopen("wombats.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d%d", &R, &C);
    for (i = 0; i < R; ++i)
        for (j = 0; j < C-1; ++j)
            res = fscanf(f, "%d", &H[i][j]);
    for (i = 0; i < R-1; ++i)
        for (j = 0; j < C; ++j)
            res = fscanf(f, "%d", &V[i][j]);

    init(R, C, H, V);

    res = fscanf(f, "%d", &E);
    for (i = 0; i < E; i++) {
        res = fscanf(f, "%d", &event);
        if (event == 1) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeH(P, Q, W);
        } else if (event == 2) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeV(P, Q, W);
        } else if (event == 3) {
            res = fscanf(f, "%d%d", &V1, &V2);
            printf("%d\n", escape(V1, V2));
        } else
            fail("Invalid event type.");
    }

    fclose(f);
    return 0;
}

#endif

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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13268 KB Output is correct
2 Correct 56 ms 13268 KB Output is correct
3 Correct 118 ms 14852 KB Output is correct
4 Correct 55 ms 13268 KB Output is correct
5 Correct 55 ms 13332 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 2 ms 1108 KB Output is correct
11 Correct 66 ms 2088 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12258 ms 3308 KB Output is correct
2 Correct 18288 ms 3640 KB Output is correct
3 Correct 12359 ms 3324 KB Output is correct
4 Correct 12174 ms 3324 KB Output is correct
5 Correct 12054 ms 3300 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Execution timed out 20061 ms 3364 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 18240 KB Output is correct
2 Correct 821 ms 18244 KB Output is correct
3 Correct 308 ms 18240 KB Output is correct
4 Correct 360 ms 18980 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12200 ms 3304 KB Output is correct
2 Correct 18150 ms 3740 KB Output is correct
3 Correct 12191 ms 3284 KB Output is correct
4 Correct 12129 ms 3328 KB Output is correct
5 Correct 11970 ms 3312 KB Output is correct
6 Correct 318 ms 18280 KB Output is correct
7 Correct 828 ms 18252 KB Output is correct
8 Correct 313 ms 18240 KB Output is correct
9 Correct 349 ms 18988 KB Output is correct
10 Correct 54 ms 13268 KB Output is correct
11 Correct 55 ms 13308 KB Output is correct
12 Correct 120 ms 14832 KB Output is correct
13 Correct 57 ms 13268 KB Output is correct
14 Correct 56 ms 13268 KB Output is correct
15 Correct 1 ms 980 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 2 ms 1108 KB Output is correct
20 Correct 2 ms 1108 KB Output is correct
21 Correct 2 ms 1108 KB Output is correct
22 Correct 2 ms 1108 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 72 ms 2068 KB Output is correct
26 Correct 2 ms 1108 KB Output is correct
27 Execution timed out 20045 ms 3368 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12305 ms 3304 KB Output is correct
2 Correct 18405 ms 3736 KB Output is correct
3 Correct 12273 ms 3324 KB Output is correct
4 Correct 12094 ms 3348 KB Output is correct
5 Correct 12048 ms 3300 KB Output is correct
6 Correct 315 ms 18260 KB Output is correct
7 Correct 812 ms 18224 KB Output is correct
8 Correct 316 ms 18260 KB Output is correct
9 Correct 341 ms 19004 KB Output is correct
10 Correct 55 ms 13268 KB Output is correct
11 Correct 56 ms 13268 KB Output is correct
12 Correct 118 ms 14820 KB Output is correct
13 Correct 64 ms 13268 KB Output is correct
14 Correct 55 ms 13268 KB Output is correct
15 Runtime error 151 ms 20728 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -