oj.uz

Submission #861968

# Submission time Handle Problem Language Result Execution time Memory
861968 2023-10-17T09:43:35 Z HuyQuang_re_Zero Flood (IOI07_flood) C++14
100 / 100
 198 ms 29504 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
struct point { int x,y; } a[N];
II e[2*N];
int U[N],D[N],L[N],R[N],n,m,i,u,v,mx[N],f[4*N];
bool visited[N];
vector <int> adj[4*N];
int main()
{
 //   freopen("flood.inp","r",stdin);
 //   freopen("flood.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u>>v;
        if(a[u].x>a[v].x || (a[u].x==a[v].x && a[u].y>a[v].y)) swap(u,v);
        e[i]={ u,v };
        if(a[u].x==a[v].x) U[u]=D[v]=i; else R[u]=L[v]=i;
    }


    //////////////////////////////////////////////////////////////////////////////////////

    auto BFS_point=[&](int u)
    {
        queue <int> q;
        vector <int> vec;
        int ma=0;
        q.push(u); visited[u]=1;
        while(q.size()>0)
        {
            int u=q.front(); q.pop();
            vec.push_back(u);
            ma=max(ma,a[u].x);
            auto consider=[&](int x)
            {
                if(x==0) return ;
                int v=(e[x].fst==u ? e[x].snd : e[x].fst);
                if(visited[v]) return ;
                q.push(v); visited[v]=1;
            };
            consider(U[u]);
            consider(D[u]);
            consider(L[u]);
            consider(R[u]);
        }
        for(int u:vec) mx[u]=ma;
    };
    for(u=1;u<=n;u++)
        if(visited[u]==0) BFS_point(u);


    ///////////////////////////////////////////////////////////////////////////////
    for(u=1;u<=n;u++)
    {
        auto consider=[&](II a,II b)
        {
            int u=a.fst+m*(a.snd==1 || a.snd==4),v=b.fst+m*(b.snd==2 || b.snd==3);
            adj[u].push_back(v); adj[v].push_back(u);
        };
        vector <II> vec;
        if(U[u]>0) vec.push_back({ U[u],1 });
        if(R[u]>0) vec.push_back({ R[u],2 });
        if(D[u]>0) vec.push_back({ D[u],3 });
        if(L[u]>0) vec.push_back({ L[u],4 });
        if(vec.size()==0) continue;
        if(vec.size()==1)
        {
            int u=vec[0].fst,v=vec[0].fst+m;
            adj[u].push_back(v); adj[v].push_back(u);
        }
        else
        {
            for(i=1;i<vec.size();i++) consider(vec[i-1],vec[i]);
            consider(vec.back(),vec[0]);
        }
    }


    set <II> s;
    memset(f,63,sizeof(f));
    for(i=1;i<=m;i++)
    {
        int u=e[i].fst,v=e[i].snd;
        if(a[v].x==mx[v])
        {
            if(a[u].x==a[v].x)
                s.insert({ 0,i+m }),f[i+m]=0;
            else if(U[v]==0 && D[v]==0)
                s.insert({ 0,i }),s.insert({ 0,i+m }),f[i]=f[i+m]=0;
        }
    }

    while(s.size()>0)
    {
        int u=s.begin()->snd,v; s.erase(s.begin());
        for(int v:adj[u])
            if(f[v]>f[u])
            {
                s.erase({ f[v],v });
                f[v]=f[u];
                s.insert({ f[v],v });
            }
        if(u<=m) v=u+m; else v=u-m;
        if(f[v]>f[u]+1)
        {
            s.erase({ f[v],v });
            f[v]=f[u]+1;
            s.insert({ f[v],v });
        }
    }
    int res=0;
    for(i=1;i<=m;i++) res+=(f[i]==f[i+m]);
    cout<<res<<'\n';
    for(i=1;i<=m;i++) if(f[i]==f[i+m]) cout<<i<<'\n';
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:92: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]
   92 |             for(i=1;i<vec.size();i++) consider(vec[i-1],vec[i]);
      |                     ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14952 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15092 KB Output is correct

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 3 ms 14980 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15096 KB Output is correct
2 Correct 3 ms 14996 KB Output is correct

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 17304 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 25460 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 27732 KB Output is correct
2 Correct 198 ms 29052 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 27496 KB Output is correct
2 Correct 152 ms 28480 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 28556 KB Output is correct
2 Correct 140 ms 29504 KB Output is correct