oj.uz

Submission #1051113

# Submission time Handle Problem Language Result Execution time Memory
1051113 2024-08-09T20:03:52 Z Dennis_Jason Flood (IOI07_flood) C++14
55 / 100
 56 ms 17500 KB 
#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;
    map<int,int>X,Y;
    vector<int>x_axis,y_axis;
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;
        swap(x,y);
       x_axis.pb(x);
       y_axis.pb(y);

        node[i]={x,y};
    }
    sort(x_axis.begin(),x_axis.end());
    sort(y_axis.begin(),y_axis.end());
    for(int i=1;i<=n;++i)
    {
        X[x_axis[i-1]]=i;
        Y[y_axis[i-1]]=i;
    }
    for(int i=1;i<=n;++i)
    {
        auto[x,y]=node[i];
        x=X[x];
        y=Y[y];
        node[i]={2*x,2*y};
        max_x=max(max_x,2*x);
        max_y=max(max_y,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<=1000 && max_y<=1000)
    {
        subtask1();
    }


    return 0;
}

Compilation message

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];
      |              ^
flood.cpp: In function 'int main()':
flood.cpp:178:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  178 |         auto[x,y]=node[i];
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 15452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15396 KB Output is correct
2 Correct 15 ms 15452 KB Output is correct
3 Correct 22 ms 15388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17500 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16988 KB Output is correct
2 Correct 12 ms 14172 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 17244 KB Output is correct
2 Correct 14 ms 17244 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16732 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15708 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15192 KB Output is correct
2 Correct 12 ms 13660 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14940 KB Output is correct
2 Correct 14 ms 15196 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8660 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 13364 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 15808 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 13508 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 14788 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -