oj.uz

Submission #861927

# Submission time Handle Problem Language Result Execution time Memory
861927 2023-10-17T07:45:08 Z HuyQuang_re_Zero Flood (IOI07_flood) C++14
64 / 100
 292 ms 49876 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 400005
#define II pair <ll,ll>
#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 edge { int num; short int type; };
vector <edge> adj[400005];
struct point { int x,y; } a[100005];
pair <int,int> e[200005];
int n,m,i,u,v,nangle,f[N],mx[100005],ok,alone[100005];
bool visited[100005];
vector <int> angle_to_side[200005][2];
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 };
        adj[u].push_back({ v,0 });
        adj[v].push_back({ u,0 });
    }
    auto BFS_point=[&](int u)
    {
        queue <int> q;
        vector <int> node;
        int ma=0;
        q.push(u); visited[u]=1;
        while(q.size()>0)
        {
            int u=q.front(); q.pop();
            ma=max(ma,a[u].x);
            node.push_back(u);
            for(edge x:adj[u])
                if(visited[x.num]==0) q.push(x.num),visited[x.num]=1;
        }
        for(int u:node) mx[u]=ma;
    };
    for(u=1;u<=n;u++)
        if(visited[u]==0) BFS_point(u);


    for(u=1;u<=n;u++) adj[u].clear();
    for(i=1;i<=m;i++)
    {
        int u=e[i].fst,v=e[i].snd;
        if(a[v].x>a[u].x) adj[u].push_back({ i,2 }),adj[v].push_back({ i,4 });
        if(a[v].y>a[u].y) adj[u].push_back({ i,1 }),adj[v].push_back({ i,3 });
    }


    for(u=1;u<=n;u++)
    {
        sort(adj[u].begin(),adj[u].end(),[&](edge a,edge b){ return a.type<b.type; });
        if(adj[u].size()==0) continue;
        else if(adj[u].size()==1)
        {
            edge x=adj[u].back();
            alone[u]=++nangle;
            for(i=0;i<=1;i++)
                angle_to_side[x.num][i].push_back(nangle);
        }
        else
        {
            auto consider=[&](edge a,edge b)
            {
                int oka=(a.type==1 || a.type==4),okb=(b.type==2 || b.type==3);
                nangle++;
                angle_to_side[a.num][oka].push_back(nangle);
                angle_to_side[b.num][okb].push_back(nangle);
            };
            for(i=1;i<adj[u].size();i++)
                consider(adj[u][i-1],adj[u][i]);
            consider(adj[u].back(),adj[u][0]);
        }
    }
    for(u=1;u<=n;u++) adj[u].clear();

    for(i=1;i<=m;i++)
    {
        for(ok=0;ok<=1;ok++)
        {
            u=angle_to_side[i][ok][0],v=angle_to_side[i][ok][1];
            adj[u].push_back({ v,0 }),adj[v].push_back({ u,0 });
        }
        u=angle_to_side[i][0][0],v=angle_to_side[i][1][0];
        adj[u].push_back({ v,1 }),adj[v].push_back({ u,1 });
    }


    memset(f,63,sizeof(f));
    set <pair <int,int> > s;
    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)
                for(int u:angle_to_side[i][1])
                    s.insert({ 0,u }),f[u]=0;
            else if(alone[v]>0)
                s.insert({ 0,alone[v] }),f[alone[v]]=0;
        }
    }
    while(s.size()>0)
    {
        int u=s.begin()->snd; s.erase(s.begin());
        for(edge x:adj[u])
        {
            int v=x.num,k=x.type;
            if(f[v]>f[u]+k)
            {
                s.erase({ f[v],v });
                f[v]=f[u]+k;
                s.insert({ f[v],v });
            }
        }
    }
    int res=0;
    for(i=1;i<=m;i++)
    {
        int u=angle_to_side[i][0][0],v=angle_to_side[i][1][0];
        if(f[u]==f[v]) res++;
    }
    cout<<res<<'\n';
    for(i=1;i<=m;i++)
    {
        int u=angle_to_side[i][0][0],v=angle_to_side[i][1][0];
        if(f[u]==f[v]) cout<<i<<'\n';
    }
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(i=1;i<adj[u].size();i++)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 4 ms 23992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 24152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23900 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24152 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 24040 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 24052 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 40792 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 42836 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 250 ms 47048 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 292 ms 49876 KB Memory limit exceeded
2 Halted 0 ms 0 KB -