Submission #1051108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051108		Dennis_Jason	Flood (IOI07_flood)	C++14	43 / 100	35 ms	16952 KiB

flood

#include <bits/stdc++.h>
#define NMAX 200001
//#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF  1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*-------------Initialize------------*/
struct nod{
    int x, y;
}node[NMAX];
struct edge{
    int node,up,right,down,left;
};
vector<vector<edge>>G(NMAX);
vector<pii>edges;
bool alive[NMAX];
int n,w,max_x,max_y;
int di[]={0,0,1,-1};
int dj[]={1,-1,0,0};
int mat[1010][1010];
int tim[1010][1010];

/*-------positions of wall a->b--------- */
edge wall_pos(int a,int b)
{
    int left=min(node[a].x,node[b].x);
    int right=max(node[a].x,node[b].x);
    int up=min(node[a].y,node[b].y);
    int down=max(node[a].y,node[b].y);
    return{b,up,right,down,left};
}
/*-----Subtask1(x,y<=500)-------*/
void subtask1()
{


    for(int i=1;i<=n;++i)
    {
        mat[node[i].x][node[i].y]=i;
    }
    auto draw_edge=[&](int x,int y){
        int imin=min(node[x].x,node[y].x);
        int imax=max(node[x].x,node[y].x);
        int jmin=min(node[x].y,node[y].y);
        int jmax=max(node[x].y,node[y].y);

        for(int i=imin;i<=imax;++i)
        {
            for (int j=jmin;j<=jmax;++j)
            {
                if(!mat[i][j])
                    mat[i][j]=-1;
            }
        }
    };

    for(auto [x,y]:edges)
    {
        draw_edge(x,y);
    }
    auto inmat=[&](int i,int j)
    {
        return i>=0 && i<=1001 && j>=0 && j<=1001;
    };
    deque<pii>dq;
    dq.push_front({0,0});
    tim[0][0]=1;
    while(!dq.empty())
    {
        auto [x,y]=dq.front();
//        cout<<x<<" "<<y<<nl;
        dq.pop_front();
        for(int d=0;d<4;++d)
        {
            int inou=x+di[d];
            int jnou=y+dj[d];
            if(inmat(inou,jnou) && !tim[inou][jnou])
            {
                int weight=0;
                if(mat[inou][jnou]!=0)
                    weight=1;
                tim[inou][jnou]=tim[x][y]+weight;
                if(weight)
                    dq.push_back({inou,jnou});
                else
                    dq.push_front({inou,jnou});
            }
        }
    }
    int ans=w;
    auto alive_=[&](int x,int y,int ind){
        int imin=min(node[x].x,node[y].x);
        int imax=max(node[x].x,node[y].x);
        int jmin=min(node[x].y,node[y].y);
        int jmax=max(node[x].y,node[y].y);
        bool ok=true;
        if(imin==imax)
        {
            for(int j=jmin+1;j<jmax;++j)
            {
                if(tim[imin-1][j]!=tim[imin+1][j])
                    ok=false;
            }
        }
        else
        {
            for(int i=imin+1;i<imax;++i)
            {
                if(tim[i][jmin-1]!=tim[i][jmin+1])
                    ok=false;
            }
        }
        if(!ok)
            ans--;
        alive[ind]=ok;
    };

    for(int i=1;i<=w;++i)
    {
        auto [x,y]=edges[i-1];
        alive_(x,y,i);
    }
    cout<<ans<<nl;
    for(int i=1;i<=w;++i)
    {
        if(alive[i])
            cout<<i<<nl;
    }
//    for(int i=0;i<=20;++i)
//    {
//        for(int j=0;j<=20;++j)
//        {
//            cout<<tim[i][j]<<" ";
//        }
//        cout<<nl;
//    }
return;


}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;
        swap(x,y);
        max_x=max(max_x,2*x);
        max_y=max(max_y,2*y);
        node[i]={2*x,2*y};
    }
    cin>>w;
    for(int i=1;i<=w;++i)
    {
        int x,y;
        cin>>x>>y;
        edges.pb({x,y});
        G[x].pb(wall_pos(x,y));
        alive[i]=true;
    }
    if(max_x<=2000 && max_y<=2000)
    {
        subtask1();
    }
    else if(n<=500)
    {
        cout<<0;
    }


    return 0;
}

Compilation message (stderr)

flood.cpp:9: warning: "LLONG_MAX" redefined
    9 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from flood.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      | 
flood.cpp: In function 'void subtask1()':
flood.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [x,y]:edges)
      |              ^
flood.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |         auto [x,y]=dq.front();
      |              ^
flood.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |         auto [x,y]=edges[i-1];
      |              ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9