oj.uz

Submission #1022293

# Submission time Handle Problem Language Result Execution time Memory
1022293 2024-07-13T11:53:45 Z MarwenElarbi Wombats (IOI13_wombats) C++17
12 / 100
 4562 ms 10844 KB 
#include <bits/stdc++.h>
#include"wombats.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int nax=1e5+5;
vector<pair<int,int>> adj[nax];
int r,c;
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]) {
    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) {
    for (int i = 0; i < adj[P].size(); ++i)
    {
        if(adj[P][i].fi==Q) adj[P][i].se=W;
    }
    for (int i = 0; i < adj[Q].size(); ++i)
    {
        if(adj[Q][i].fi==P) adj[Q][i].se=W;
    }
}

void changeV(int P, int Q, int W) {
    for (int i = 0; i < adj[P].size(); ++i)
    {
        if(adj[P][i].fi==Q) adj[P][i].se=W;
    }
    for (int i = 0; i < adj[Q].size(); ++i)
    {
        if(adj[Q][i].fi==P) adj[Q][i].se=W;
    }
}

int escape(int V1, int V2) {
    return djikastra(V1,V2);
}/*
static int h[5000][200];
static int v[5000][200];
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int R,C;
    cin>>R>>C;
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C-1; ++j)
        {
            cin>>h[i][j];
        }
    }
    for (int i = 0; i < R-1; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            cin>>v[i][j];
        }
    }
    init(R,C,h,v);
    int e;
    cin>>e;
    while(e--){
        int c;
        cin>>c;
        if(c==1){
            int p,q,w;
            cin>>p>>q>>w;
            changeH(p,q,w);
        }else if(c==2){
            int p,q,w;
            cin>>p>>q>>w;
            changeV(p,q,w);
        }else{
            int v1,v2;
            cin>>v1>>v2;
            cout <<escape(v1,v2)<<endl;
        }
    }
}*/

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:67: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]
   67 |     for (int i = 0; i < adj[P].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
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[Q].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:78: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]
   78 |     for (int i = 0; i < adj[P].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
wombats.cpp:82: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]
   82 |     for (int i = 0; i < adj[Q].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
wombats.cpp: In function 'long long int djikastra(int, int)':
wombats.cpp:25:80: warning: control reaches end of non-void function [-Wreturn-type]
   25 |     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      |                                                                                ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6748 KB Output is correct
2 Incorrect 50 ms 6748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 8 ms 2652 KB Output is correct
5 Correct 5 ms 2880 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 7 ms 2652 KB Output is correct
8 Correct 9 ms 2652 KB Output is correct
9 Correct 14 ms 2876 KB Output is correct
10 Correct 9 ms 2652 KB Output is correct
11 Correct 4562 ms 5108 KB Output is correct
12 Correct 11 ms 2884 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 3500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -