oj.uz

Submission #197545

# Submission time Handle Problem Language Result Execution time Memory
197545 2020-01-21T16:00:23 Z SamAnd Flood (IOI07_flood) C++17
55 / 100
 287 ms 22608 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N=100005,M=502;
const int xx[4]={-1,1,0,0};
const int yy[4]={0,0,-1,1};
struct ban
{
    int x,y;
};

int n,m;
ban a[N],b[N];

int u[M][M];

int k;
int c[M][M];
void dfs(int x,int y)
{
    c[x][y]=k;
    for(int i=0;i<4;++i)
    {
        if(!(u[x][y]&(1<<i)))
            continue;
        int hx=x+xx[i];
        int hy=y+yy[i];
        if(hx>=0 && hx<M && hy>=0 && hy<M && !c[hx][hy])
            dfs(hx,hy);
    }
}

vector<int> g[N];
int d[N];
void bfs()
{
    queue<int> q;
    d[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<g[x].size();++i)
        {
            int h=g[x][i];
            if(!d[h])
            {
                d[h]=d[x]+1;
                q.push(h);
            }
        }
    }
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    map<int,int> mpx,mpy;
    vector<int> vx,vy;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a[i].x>>a[i].y;
        vx.push_back(a[i].x);
        vy.push_back(a[i].y);
    }
    sort(vx.begin(),vx.end());
    int z=1;
    for(int i=0;i<vx.size();++i)
    {
        if(!i || vx[i]!=vx[i-1])
            mpx[vx[i]]=z++;
    }
    sort(vy.begin(),vy.end());
    z=1;
    for(int i=0;i<vy.size();++i)
    {
        if(!i || vy[i]!=vy[i-1])
            mpy[vy[i]]=z++;
    }
    for(int i=0;i<n;++i)
    {
        a[i].x=mpx[a[i].x];
        a[i].y=mpy[a[i].y];
    }
    cin>>m;
    for(int i=0;i<m;++i)
    {
        cin>>b[i].x>>b[i].y;
        --b[i].x;
        --b[i].y;
    }
    ///////////////////////////////////
    for(int x=0;x<M;++x)
    {
        for(int y=0;y<M;++y)
        {
            u[x][y]=(1<<4)-1;
        }
    }
    for(int k=0;k<m;++k)
    {
        int i=b[k].x;
        int j=b[k].y;
        if(a[i].x==a[j].x)
        {
            for(int y=min(a[i].y,a[j].y);y<max(a[i].y,a[j].y);++y)
            {
                u[a[i].x][y]=(u[a[i].x][y])^(1<<0);
                u[a[i].x-1][y]=(u[a[i].x-1][y])^(1<<1);
            }
        }
        else
        {
            for(int x=min(a[i].x,a[j].x);x<max(a[i].x,a[j].x);++x)
            {
                u[x][a[i].y]=(u[x][a[i].y])^(1<<2);
                u[x][a[i].y-1]=(u[x][a[i].y-1])^(1<<3);
            }
        }
    }
    for(int x=0;x<M;++x)
    {
        for(int y=0;y<M;++y)
        {
            if(!c[x][y])
            {
                ++k;
                dfs(x,y);
            }
        }
    }
    for(int k=0;k<m;++k)
    {
        int i=b[k].x;
        int j=b[k].y;
        if(a[i].x==a[j].x)
        {
            int y=min(a[i].y,a[j].y);
            g[c[a[i].x][y]].push_back(c[a[i].x-1][y]);
            g[c[a[i].x-1][y]].push_back(c[a[i].x][y]);
        }
        else
        {
            int x=min(a[i].x,a[j].x);
            g[c[x][a[i].y]].push_back(c[x][a[i].y-1]);
            g[c[x][a[i].y-1]].push_back(c[x][a[i].y]);
        }
    }
    bfs();
    vector<int> ans;
    for(int k=0;k<m;++k)
    {
        int i=b[k].x;
        int j=b[k].y;
        if(a[i].x==a[j].x)
        {
            int y=min(a[i].y,a[j].y);
            if(d[c[a[i].x][y]]==d[c[a[i].x-1][y]])
                ans.push_back(k+1);
        }
        else
        {
            int x=min(a[i].x,a[j].x);
            if(d[c[x][a[i].y]]==d[c[x][a[i].y-1]])
                ans.push_back(k+1);
        }
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();++i)
        cout<<ans[i]<<endl;
    return 0;
}

Compilation message

flood.cpp: In function 'void bfs()':
flood.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<g[x].size();++i)
                     ~^~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vx.size();++i)
                 ~^~~~~~~~~~
flood.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vy.size();++i)
                 ~^~~~~~~~~~
flood.cpp:172:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();++i)
                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16504 KB Output is correct
2 Correct 33 ms 16504 KB Output is correct
3 Correct 28 ms 16564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16376 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15752 KB Output is correct
2 Correct 28 ms 16424 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16120 KB Output is correct
2 Correct 26 ms 16380 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16436 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15224 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14580 KB Output is correct
2 Correct 27 ms 15864 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13944 KB Output is correct
2 Correct 28 ms 16376 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 12892 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 18012 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 22608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 281 ms 15792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 287 ms 15724 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -