oj.uz

Submission #683332

# Submission time Handle Problem Language Result Execution time Memory
683332 2023-01-18T07:56:55 Z groshi Wall (CEOI14_wall) C++17
100 / 100
 610 ms 171764 KB 
#include<bits/stdc++.h>
using namespace std;
int t[500][500];
int kraw1[500][500];
int kraw2[500][500];
long long odw[200000];
int skad[200000];
bool bylo[200000];
vector<pair<int,int> > Q;
map<int,int> krawedz[700000];
map<int,bool> specjalna[700000];
int n,m;
struct wi{
    vector<pair<int,int> > Q;
    int bylo=0;
    long long odw=0;
}*w;
void dodaj(int x)
{
    while(x!=0)
    {
        specjalna[x][skad[x]]=1;
        specjalna[skad[x]][x]=1;
        x=skad[x];
    }
}
void obwod(int x1,int y1)
{
    int x=(x1-1)*(m+1)+y1-1;
    int y=(x1-1)*(m+1)+y1;
    specjalna[x][y]=1;
    specjalna[y][x]=1;
    x=x1*(m+1)+y1;
    specjalna[x][y]=1;
    specjalna[y][x]=1;
    y=x1*(m+1)+y1-1;
    specjalna[x][y]=1;
    specjalna[y][x]=1;
    x=(x1-1)*(m+1)+y1-1;
    specjalna[x][y]=1;
    specjalna[y][x]=1;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    w=new wi[4*(n+1)*(m+1)+100];
    int d[4]={m+1,-(m+1),1,-1};
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>t[i][j];
            if(t[i][j])
                Q.push_back({i,j});
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+1;j++)
        {
            cin>>kraw1[i][j];
            int x1=(i-1)*(m+1)+j-1;
            int y1=i*(m+1)+j-1;
            krawedz[x1][y1]=kraw1[i][j];
            krawedz[y1][x1]=kraw1[i][j];
        }
    for(int i=1;i<=n+1;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>kraw2[i][j];
            int x1=(i-1)*(m+1)+j-1;
            int y1=(i-1)*(m+1)+j;
            krawedz[x1][y1]=kraw2[i][j];
            krawedz[y1][x1]=kraw2[i][j];
        }
    priority_queue<pair<long long,pair<int,int> > > kolejka;
    kolejka.push({0,{0,0}});
    while(!kolejka.empty())
    {
        auto para=kolejka.top();
        kolejka.pop();
        int x=para.second.first;
        if(bylo[x])
            continue;
        bylo[x]=1;
        odw[x]=-para.first;
        skad[x]=para.second.second;
        for(int i=0;i<4;i++)
        {
            int x1=d[i]+x;
            if(odw[x1] || krawedz[x].count(x1)==0)
                continue;
            kolejka.push({para.first-krawedz[x][x1],{x1,x}});
        }
    }
    for(int i=0;i<Q.size();i++)
    {
        int x1=Q[i].first;
        int y1=Q[i].second;
        int x=(x1-1)*(m+1)+y1-1;
        dodaj(x);
        obwod(x1,y1);
    }
    for(int i=0;i<=n*(m+1)+m;i++)
    {
        for(int a=0;a<4;a++)
        {
            int x=i+d[a];
            if(specjalna[i].count(x)==0 && a==0)
            {
                w[i*4+3].Q.push_back({i*4+2,0});
                w[i*4+2].Q.push_back({i*4+3,0});
            }
            if(specjalna[i].count(x)==0 && i!=0 && a==1)
            {
                w[i*4].Q.push_back({i*4+1,0});
                w[i*4+1].Q.push_back({i*4,0});
            }
            if(specjalna[i].count(x)==0 && a==2)
            {
                w[i*4+1].Q.push_back({i*4+2,0});
                w[i*4+2].Q.push_back({i*4+1,0});
            }
            if(specjalna[i].count(x)==0 && a==3)
            {
                w[i*4+3].Q.push_back({i*4,0});
                w[i*4].Q.push_back({i*4+3,0});
            }
            if(krawedz[i].count(x))
            {
                if(a==0)
                {
                    int x1=i*4+3;
                    int y1=x*4;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                    x1=i*4+2;
                    y1=x*4+1;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                }
                if(a==1)
                {
                    int x1=i*4;
                    int y1=x*4+3;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                    x1=i*4+1;
                    y1=x*4+2;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                }
                if(a==2)
                {
                    int x1=i*4+1;
                    int y1=x*4;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                    x1=i*4+2;
                    y1=x*4+3;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                }
                if(a==3)
                {
                    int x1=i*4;
                    int y1=x*4+1;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                    x1=i*4+3;
                    y1=x*4+2;
                    w[x1].Q.push_back({y1,krawedz[i][x]});
                }
            }
        }
    }
    priority_queue<pair<long long,int> > kolejka1;
    kolejka1.push({0,0});
    while(!kolejka1.empty())
    {
        auto para=kolejka1.top();
        kolejka1.pop();
        int x=para.second;
        if(w[x].bylo)
            continue;
        w[x].odw=-para.first;
        w[x].bylo=1;
        for(int i=0;i<w[x].Q.size();i++)
        {
            int pom=w[x].Q[i].first;
            if(w[pom].bylo)
                continue;
            kolejka1.push({para.first-w[x].Q[i].second,pom});
        }
    }
    cout<<w[1].odw;
    return 0;
}

Compilation message

wall.cpp: In function 'int32_t main()':
wall.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=0;i<Q.size();i++)
      |                 ~^~~~~~~~~
wall.cpp:181:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for(int i=0;i<w[x].Q.size();i++)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 66108 KB Output is correct
2 Correct 31 ms 66168 KB Output is correct
3 Correct 31 ms 66240 KB Output is correct
4 Correct 31 ms 66152 KB Output is correct
5 Correct 31 ms 66132 KB Output is correct
6 Correct 33 ms 66772 KB Output is correct
7 Correct 35 ms 66696 KB Output is correct
8 Correct 33 ms 66788 KB Output is correct
9 Correct 35 ms 66580 KB Output is correct
10 Correct 39 ms 66792 KB Output is correct
11 Correct 34 ms 66996 KB Output is correct
12 Correct 34 ms 67156 KB Output is correct
13 Correct 36 ms 67284 KB Output is correct
14 Correct 34 ms 67116 KB Output is correct
15 Correct 33 ms 67000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 67284 KB Output is correct
2 Correct 35 ms 67304 KB Output is correct
3 Correct 35 ms 67228 KB Output is correct
4 Correct 37 ms 67304 KB Output is correct
5 Correct 37 ms 67284 KB Output is correct
6 Correct 40 ms 67216 KB Output is correct
7 Correct 37 ms 67352 KB Output is correct
8 Correct 38 ms 67216 KB Output is correct
9 Correct 35 ms 67308 KB Output is correct
10 Correct 36 ms 67328 KB Output is correct
11 Correct 51 ms 67196 KB Output is correct
12 Correct 35 ms 67228 KB Output is correct
13 Correct 33 ms 67352 KB Output is correct
14 Correct 35 ms 67228 KB Output is correct
15 Correct 36 ms 67320 KB Output is correct
16 Correct 36 ms 67412 KB Output is correct
17 Correct 35 ms 67276 KB Output is correct
18 Correct 41 ms 67172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 90552 KB Output is correct
2 Correct 120 ms 86400 KB Output is correct
3 Correct 115 ms 87980 KB Output is correct
4 Correct 122 ms 88396 KB Output is correct
5 Correct 373 ms 123236 KB Output is correct
6 Correct 126 ms 89932 KB Output is correct
7 Correct 311 ms 123676 KB Output is correct
8 Correct 255 ms 120304 KB Output is correct
9 Correct 247 ms 120132 KB Output is correct
10 Correct 301 ms 123696 KB Output is correct
11 Correct 337 ms 127408 KB Output is correct
12 Correct 124 ms 90664 KB Output is correct
13 Correct 258 ms 118620 KB Output is correct
14 Correct 610 ms 158064 KB Output is correct
15 Correct 423 ms 157572 KB Output is correct
16 Correct 411 ms 158848 KB Output is correct
17 Correct 547 ms 164908 KB Output is correct
18 Correct 550 ms 171764 KB Output is correct
19 Correct 588 ms 160532 KB Output is correct
20 Correct 438 ms 158456 KB Output is correct