제출 #1022414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022414		MarwenElarbi	웜뱃 (IOI13_wombats)	C++17	55 / 100	20065 ms	96876 KiB

wombats

#include <bits/stdc++.h>
#include"wombats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
vector<pair<int,int>> adj[5005*205];
int r,c;
int ans[205][205];
int convert(int x,int y){
    return x*c+y;
}
long long dis[5005*205];
long long djikastra(int x,int y){
    x=convert(0,x);
    y=convert(r-1,y);
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            dis[convert(i,j)]=1e18;
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    pq.push({0,x});
    dis[x]=0;
    while(!pq.empty()){
        int node=pq.top().se;
        long long d=pq.top().fi;
        pq.pop();
        if(node==y) return d;
        if(d>dis[node]) continue;
        for(auto u:adj[node]){
            long long newd=d+u.se;
            if(newd>=dis[u.fi]) continue;
            dis[u.fi]=newd;
            pq.push({newd,u.fi});
        }
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    memset(ans,-1,sizeof ans);
    r=R;
    c=C;
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C-1; ++j)
        {
            int x=convert(i,j);
            int y=convert(i,j+1);
            adj[x].pb({y,H[i][j]});
            adj[y].pb({x,H[i][j]});
        }
    }
    for (int i = 0; i < R-1; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            int x=convert(i,j);
            int y=convert(i+1,j);
            adj[x].pb({y,V[i][j]});
        }
    }
    return;
}
void changeH(int P, int Q, int W) {
    memset(ans,-1,sizeof ans);
    for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
    {
        if(adj[convert(P,Q)][i].fi==convert(P,Q+1)) adj[convert(P,Q)][i].se=W;
    }
    for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
    {
        if(adj[convert(P,Q+1)][i].fi==convert(P,Q)) adj[convert(P,Q+1)][i].se=W;
    }
}
 
void changeV(int P, int Q, int W) {
    memset(ans,-1,sizeof ans);
    for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
    {
        if(adj[convert(P,Q)][i].fi==convert(P+1,Q)) adj[convert(P,Q)][i].se=W;
    }
}
 
int escape(int V1, int V2) {
    if(ans[V1][V2]!=-1) return ans[V1][V2];
    return ans[V1][V2]=djikastra(V1,V2);
}

컴파일 시 표준 에러 (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;
      |      ^~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < adj[convert(P,Q+1)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < adj[convert(P,Q)].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
wombats.cpp: In function 'long long int djikastra(int, int)':
wombats.cpp:27:80: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      |                                                                                ^~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24