oj.uz

답안 #1022414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1022414 2024-07-13T13:17:22 Z MarwenElarbi 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 96876 KB 
#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);
}

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: 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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 28764 KB Output is correct
2 Correct 63 ms 28764 KB Output is correct
3 Correct 98 ms 31572 KB Output is correct
4 Correct 56 ms 28760 KB Output is correct
5 Correct 55 ms 28704 KB Output is correct
6 Correct 11 ms 24668 KB Output is correct
7 Correct 11 ms 24588 KB Output is correct
8 Correct 14 ms 24628 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 12 ms 24664 KB Output is correct
3 Correct 12 ms 24668 KB Output is correct
4 Correct 19 ms 24668 KB Output is correct
5 Correct 15 ms 24668 KB Output is correct
6 Correct 15 ms 24668 KB Output is correct
7 Correct 18 ms 24668 KB Output is correct
8 Correct 18 ms 24668 KB Output is correct
9 Correct 19 ms 24780 KB Output is correct
10 Correct 19 ms 24668 KB Output is correct
11 Correct 63 ms 26964 KB Output is correct
12 Correct 21 ms 24788 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 25432 KB Output is correct
2 Correct 104 ms 25432 KB Output is correct
3 Correct 105 ms 25436 KB Output is correct
4 Correct 104 ms 25432 KB Output is correct
5 Correct 104 ms 25436 KB Output is correct
6 Correct 12 ms 24668 KB Output is correct
7 Correct 11 ms 24572 KB Output is correct
8 Correct 15 ms 24520 KB Output is correct
9 Correct 143 ms 25436 KB Output is correct
10 Correct 11 ms 24668 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 32852 KB Output is correct
2 Correct 627 ms 32860 KB Output is correct
3 Correct 272 ms 32860 KB Output is correct
4 Correct 538 ms 34388 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 25436 KB Output is correct
2 Correct 109 ms 25432 KB Output is correct
3 Correct 104 ms 25432 KB Output is correct
4 Correct 107 ms 25680 KB Output is correct
5 Correct 103 ms 25496 KB Output is correct
6 Correct 263 ms 32856 KB Output is correct
7 Correct 655 ms 32860 KB Output is correct
8 Correct 263 ms 32860 KB Output is correct
9 Correct 541 ms 34124 KB Output is correct
10 Correct 63 ms 28764 KB Output is correct
11 Correct 57 ms 28764 KB Output is correct
12 Correct 99 ms 31572 KB Output is correct
13 Correct 62 ms 28760 KB Output is correct
14 Correct 57 ms 28764 KB Output is correct
15 Correct 12 ms 24664 KB Output is correct
16 Correct 11 ms 24672 KB Output is correct
17 Correct 12 ms 24788 KB Output is correct
18 Correct 23 ms 24668 KB Output is correct
19 Correct 16 ms 24668 KB Output is correct
20 Correct 15 ms 24668 KB Output is correct
21 Correct 17 ms 24664 KB Output is correct
22 Correct 18 ms 24672 KB Output is correct
23 Correct 19 ms 24668 KB Output is correct
24 Correct 18 ms 24544 KB Output is correct
25 Correct 62 ms 27060 KB Output is correct
26 Correct 20 ms 24668 KB Output is correct
27 Correct 147 ms 25688 KB Output is correct
28 Execution timed out 20065 ms 63316 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 25432 KB Output is correct
2 Correct 105 ms 25432 KB Output is correct
3 Correct 109 ms 25508 KB Output is correct
4 Correct 104 ms 25436 KB Output is correct
5 Correct 103 ms 25436 KB Output is correct
6 Correct 259 ms 32856 KB Output is correct
7 Correct 645 ms 32964 KB Output is correct
8 Correct 264 ms 33104 KB Output is correct
9 Correct 551 ms 34128 KB Output is correct
10 Correct 58 ms 28760 KB Output is correct
11 Correct 56 ms 28828 KB Output is correct
12 Correct 95 ms 31480 KB Output is correct
13 Correct 56 ms 28764 KB Output is correct
14 Correct 55 ms 28760 KB Output is correct
15 Correct 652 ms 96876 KB Output is correct
16 Execution timed out 20054 ms 95060 KB Time limit exceeded
17 Halted 0 ms 0 KB -