Submission #197545

#	Time	Username	Problem	Language	Result	Execution time	Memory
197545		SamAnd	Flood (IOI07_flood)	C++17	55 / 100	287 ms	22608 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9