oj.uz

답안 #805559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
805559 2023-08-03T17:51:36 Z YassirSalama 웜뱃 (IOI13_wombats) C++17
0 / 100
 120 ms 262144 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(MAXR*MAXC,vector<ll>(MAXR*MAXC,INF));
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<MAXR*MAXC;i++) {
        for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
    }
    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=0;j<MAXR*MAXC;j++){
            dist2[i][j]=min(dist2[i][j],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<MAXR*MAXC;i++) {
        for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
    }
    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=0;j<MAXR*MAXC;j++){
            dist2[i][j]=min(dist2[i][j],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<MAXR*MAXC;i++) {
        for(int j=0;j<MAXR*MAXC;j++) dist2[i][j]=INF;
    }
    for(int i=0;i<c;i++){
        vector<ll> dist=dijkstra(i);
        for(int j=0;j<MAXR*MAXC;j++){
            dist2[i][j]=min(dist2[i][j],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];
}


#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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 100 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 108 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 120 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 98 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 101 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 116 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -