oj.uz

Submission #755301

# Submission time Handle Problem Language Result Execution time Memory
755301 2023-06-09T17:37:11 Z Rafi22 Fountain Parks (IOI21_parks) C++17
5 / 100
 919 ms 111748 KB 
#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;
map<int,int>id[N];
map<int,int>id1[N];
vector<int>G[3*N];
bool odw[3*N];
int Pair[3*N];

int r[N];

int Find(int v)
{
    if(r[v]==v) return v;
    return r[v]=Find(r[v]);
}
void Union(int u,int v)
{
    r[u]=v;
}

int dx[4]={2,-2,0,0};
int dy[4]={0,0,2,-2};

void edge(int u,int v)
{
    G[u].pb(v);
    G[v].pb(u);
}

bool match(int v)
{
    if(odw[v]) return 0;
    odw[v]=1;
    for(auto u:G[v])
    {
        if(!Pair[u]&&!odw[u])
        {
            Pair[u]=v;
            Pair[v]=u;
            return 1;
        }
    }
    for(auto u:G[v])
    {
        if(!odw[u]&&match(Pair[u]))
        {
            Pair[u]=v;
            Pair[v]=u;
            return 1;
        }
    }
    return 0;
}
/*
void build(vector<int>u,vector<int>v,vector<int>a,vector<int>b)
{
    for(int i=0;i<sz(u);i++)
    {
        cout<<u[i]<<" "<<v[i]<<" "<<a[i]<<" "<<b[i]<<endl;
    }
}*/


int construct_roads(vector<int>x,vector<int>y)
{
    int n=sz(x);
    for(int i=0;i<n;i++)
    {
        id[x[i]][y[i]]=i+1;
        r[i+1]=i+1;
    }
    int cnt=0,it=n-1;
    vector<int>U,V,A,B;
    vector<pair<int,int>>Q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<4;j++)
        {
            int nx=x[i]+dx[j],ny=y[i]+dy[j];
            if(id[nx][ny]>0&&Find(id[nx][ny])!=Find(i+1))
            {
                cnt++;
                U.pb(id[nx][ny]-1);
                V.pb(i);
                Union(Find(id[nx][ny]),Find(i+1));
                int X=min(x[i],x[id[nx][ny]-1]),Y=min(y[i],y[id[nx][ny]-1]);
                if(x[i]==x[id[nx][ny]-1])
                {
                    if(id1[X+1][Y+1]==0)
                    {
                        id1[X+1][Y+1]=++it;
                        Q.pb({X+1,Y+1});
                    }
                    if(id1[X+1][Y-1]==0)
                    {
                        id1[X+1][Y-1]=++it;
                        Q.pb({X+1,Y-1});
                    }
                    edge(id1[X+1][Y+1],cnt);
                    edge(id1[X+1][Y-1],cnt);
                }
                else
                {
                    if(id1[X+1][Y+1]==0)
                    {
                        id1[X+1][Y+1]=++it;
                        Q.pb({X+1,Y+1});
                    }
                    if(id1[X-1][Y+1]==0)
                    {
                        id1[X-1][Y+1]=++it;
                        Q.pb({X-1,Y+1});
                    }
                    edge(id1[X+1][Y+1],cnt);
                    edge(id1[X-1][Y+1],cnt);
                }
            }
        }

    }
    if(cnt!=n-1) return 0;
    while(true)
    {
        memset(odw,0,sizeof odw);
        bool xd=0;
        for(int i=1;i<=it;i++) if(!Pair[i]) xd|=match(i);
        if(!xd) break;
    }
    for(int i=1;i<=n-1;i++)
    {
        A.pb(Q[Pair[i]-n].st);
        B.pb(Q[Pair[i]-n].nd);
        if(Pair[i]==0) return 2137;
    }
    build(U,V,A,B);
    return 1;
}

/*
int main()
{
    construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
    return 0;
}

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct
17 Correct 16 ms 33688 KB Output is correct
18 Correct 16 ms 33748 KB Output is correct
19 Incorrect 16 ms 33696 KB Tree (a[4], b[4]) = (1, 3) is not adjacent to edge between u[4]=3 @(4, 2) and v[4]=2 @(2, 2)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct
17 Correct 16 ms 33688 KB Output is correct
18 Correct 16 ms 33748 KB Output is correct
19 Incorrect 16 ms 33696 KB Tree (a[4], b[4]) = (1, 3) is not adjacent to edge between u[4]=3 @(4, 2) and v[4]=2 @(2, 2)
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct
17 Correct 17 ms 33748 KB Output is correct
18 Correct 16 ms 33692 KB Output is correct
19 Correct 16 ms 33108 KB Output is correct
20 Incorrect 683 ms 111748 KB Tree (a[1], b[1]) = (195233, 4769) is not adjacent to edge between u[1]=114192 @(195232, 4770) and v[1]=0 @(195232, 4772)
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct
17 Incorrect 919 ms 108280 KB Tree (a[161741], b[161741]) = (3, 1) is not adjacent to edge between u[161741]=199575 @(2, 2) and v[161741]=112394 @(2, 4)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33748 KB Output is correct
2 Correct 17 ms 33740 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 17 ms 33748 KB Output is correct
5 Correct 17 ms 33764 KB Output is correct
6 Correct 17 ms 33244 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 16 ms 33148 KB Output is correct
9 Correct 508 ms 76644 KB Output is correct
10 Correct 37 ms 38076 KB Output is correct
11 Correct 153 ms 56608 KB Output is correct
12 Correct 48 ms 40160 KB Output is correct
13 Correct 108 ms 46148 KB Output is correct
14 Correct 19 ms 33364 KB Output is correct
15 Correct 21 ms 33748 KB Output is correct
16 Correct 537 ms 76572 KB Output is correct
17 Correct 16 ms 33688 KB Output is correct
18 Correct 16 ms 33748 KB Output is correct
19 Incorrect 16 ms 33696 KB Tree (a[4], b[4]) = (1, 3) is not adjacent to edge between u[4]=3 @(4, 2) and v[4]=2 @(2, 2)
20 Halted 0 ms 0 KB -