Submission #805574

#	Time	Username	Problem	Language	Result	Execution time	Memory
805574		YassirSalama	Wombats (IOI13_wombats)	C++17	39 / 100	20061 ms	20728 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24