oj.uz

Submission #755304

# Submission time Handle Problem Language Result Execution time Memory
755304 2023-06-09T17:52:11 Z Rafi22 Fountain Parks (IOI21_parks) C++17
55 / 100
 1400 ms 165404 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({2, 2, 4, 4}, {2, 4, 2, 4});
    return 0;
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct
17 Correct 16 ms 33748 KB Output is correct
18 Correct 16 ms 33732 KB Output is correct
19 Correct 17 ms 33748 KB Output is correct
20 Correct 17 ms 33780 KB Output is correct
21 Correct 20 ms 33120 KB Output is correct
22 Correct 16 ms 33696 KB Output is correct
23 Correct 1298 ms 96448 KB Output is correct
24 Correct 17 ms 33748 KB Output is correct
25 Correct 24 ms 34088 KB Output is correct
26 Correct 24 ms 33860 KB Output is correct
27 Correct 25 ms 34176 KB Output is correct
28 Correct 483 ms 58616 KB Output is correct
29 Correct 745 ms 71528 KB Output is correct
30 Correct 1100 ms 83504 KB Output is correct
31 Correct 1352 ms 96472 KB Output is correct
32 Correct 15 ms 33716 KB Output is correct
33 Correct 18 ms 33748 KB Output is correct
34 Correct 16 ms 33748 KB Output is correct
35 Correct 18 ms 33128 KB Output is correct
36 Correct 17 ms 33184 KB Output is correct
37 Correct 17 ms 33748 KB Output is correct
38 Correct 16 ms 33800 KB Output is correct
39 Correct 16 ms 33692 KB Output is correct
40 Correct 17 ms 33748 KB Output is correct
41 Correct 16 ms 33108 KB Output is correct
42 Correct 16 ms 33696 KB Output is correct
43 Correct 20 ms 33748 KB Output is correct
44 Correct 23 ms 33996 KB Output is correct
45 Correct 625 ms 69008 KB Output is correct
46 Correct 1006 ms 84520 KB Output is correct
47 Correct 971 ms 84580 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct
17 Correct 16 ms 33748 KB Output is correct
18 Correct 16 ms 33732 KB Output is correct
19 Correct 17 ms 33748 KB Output is correct
20 Correct 17 ms 33780 KB Output is correct
21 Correct 20 ms 33120 KB Output is correct
22 Correct 16 ms 33696 KB Output is correct
23 Correct 1298 ms 96448 KB Output is correct
24 Correct 17 ms 33748 KB Output is correct
25 Correct 24 ms 34088 KB Output is correct
26 Correct 24 ms 33860 KB Output is correct
27 Correct 25 ms 34176 KB Output is correct
28 Correct 483 ms 58616 KB Output is correct
29 Correct 745 ms 71528 KB Output is correct
30 Correct 1100 ms 83504 KB Output is correct
31 Correct 1352 ms 96472 KB Output is correct
32 Correct 15 ms 33716 KB Output is correct
33 Correct 18 ms 33748 KB Output is correct
34 Correct 16 ms 33748 KB Output is correct
35 Correct 18 ms 33128 KB Output is correct
36 Correct 17 ms 33184 KB Output is correct
37 Correct 17 ms 33748 KB Output is correct
38 Correct 16 ms 33800 KB Output is correct
39 Correct 16 ms 33692 KB Output is correct
40 Correct 17 ms 33748 KB Output is correct
41 Correct 16 ms 33108 KB Output is correct
42 Correct 16 ms 33696 KB Output is correct
43 Correct 20 ms 33748 KB Output is correct
44 Correct 23 ms 33996 KB Output is correct
45 Correct 625 ms 69008 KB Output is correct
46 Correct 1006 ms 84520 KB Output is correct
47 Correct 971 ms 84580 KB Output is correct
48 Correct 16 ms 33700 KB Output is correct
49 Correct 16 ms 33696 KB Output is correct
50 Correct 16 ms 33696 KB Output is correct
51 Correct 16 ms 33692 KB Output is correct
52 Correct 17 ms 33712 KB Output is correct
53 Correct 18 ms 33716 KB Output is correct
54 Correct 16 ms 33748 KB Output is correct
55 Runtime error 1156 ms 165404 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct
17 Correct 16 ms 33748 KB Output is correct
18 Correct 16 ms 33748 KB Output is correct
19 Correct 16 ms 33108 KB Output is correct
20 Correct 769 ms 109012 KB Output is correct
21 Correct 658 ms 103512 KB Output is correct
22 Correct 767 ms 103384 KB Output is correct
23 Correct 687 ms 107388 KB Output is correct
24 Correct 515 ms 67040 KB Output is correct
25 Correct 982 ms 99852 KB Output is correct
26 Correct 973 ms 99688 KB Output is correct
27 Correct 1065 ms 111104 KB Output is correct
28 Correct 1055 ms 111080 KB Output is correct
29 Correct 1095 ms 111092 KB Output is correct
30 Correct 1080 ms 111048 KB Output is correct
31 Correct 19 ms 33748 KB Output is correct
32 Correct 55 ms 38604 KB Output is correct
33 Correct 109 ms 50464 KB Output is correct
34 Correct 612 ms 111820 KB Output is correct
35 Correct 36 ms 35680 KB Output is correct
36 Correct 141 ms 45784 KB Output is correct
37 Correct 394 ms 58504 KB Output is correct
38 Correct 413 ms 58840 KB Output is correct
39 Correct 510 ms 68020 KB Output is correct
40 Correct 705 ms 77844 KB Output is correct
41 Correct 974 ms 86240 KB Output is correct
42 Correct 1119 ms 96136 KB Output is correct
43 Correct 18 ms 33748 KB Output is correct
44 Correct 18 ms 33748 KB Output is correct
45 Correct 17 ms 33736 KB Output is correct
46 Correct 21 ms 33160 KB Output is correct
47 Correct 16 ms 33108 KB Output is correct
48 Correct 16 ms 33748 KB Output is correct
49 Correct 16 ms 33748 KB Output is correct
50 Correct 17 ms 33696 KB Output is correct
51 Correct 17 ms 33692 KB Output is correct
52 Correct 16 ms 33184 KB Output is correct
53 Correct 17 ms 33700 KB Output is correct
54 Correct 22 ms 33748 KB Output is correct
55 Correct 26 ms 33996 KB Output is correct
56 Correct 682 ms 69020 KB Output is correct
57 Correct 961 ms 84544 KB Output is correct
58 Correct 1004 ms 84528 KB Output is correct
59 Correct 16 ms 33108 KB Output is correct
60 Correct 18 ms 33748 KB Output is correct
61 Correct 16 ms 33108 KB Output is correct
62 Correct 1322 ms 115780 KB Output is correct
63 Correct 1253 ms 115924 KB Output is correct
64 Correct 1284 ms 115460 KB Output is correct
65 Correct 27 ms 34248 KB Output is correct
66 Correct 37 ms 35404 KB Output is correct
67 Correct 660 ms 67508 KB Output is correct
68 Correct 966 ms 84232 KB Output is correct
69 Correct 1400 ms 101208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct
17 Correct 936 ms 118864 KB Output is correct
18 Correct 982 ms 121088 KB Output is correct
19 Correct 804 ms 106588 KB Output is correct
20 Correct 931 ms 90280 KB Output is correct
21 Correct 945 ms 99076 KB Output is correct
22 Correct 16 ms 33872 KB Output is correct
23 Correct 124 ms 44028 KB Output is correct
24 Correct 64 ms 38164 KB Output is correct
25 Correct 252 ms 50564 KB Output is correct
26 Correct 473 ms 62992 KB Output is correct
27 Correct 501 ms 64564 KB Output is correct
28 Correct 661 ms 72292 KB Output is correct
29 Correct 790 ms 79708 KB Output is correct
30 Correct 959 ms 87212 KB Output is correct
31 Correct 1069 ms 95140 KB Output is correct
32 Correct 1307 ms 101504 KB Output is correct
33 Correct 1238 ms 115792 KB Output is correct
34 Correct 29 ms 34452 KB Output is correct
35 Correct 41 ms 35612 KB Output is correct
36 Correct 588 ms 67044 KB Output is correct
37 Correct 974 ms 83748 KB Output is correct
38 Correct 1392 ms 100524 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33792 KB Output is correct
2 Correct 17 ms 33656 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33772 KB Output is correct
5 Correct 17 ms 33748 KB Output is correct
6 Correct 18 ms 33164 KB Output is correct
7 Correct 16 ms 33108 KB Output is correct
8 Correct 19 ms 33072 KB Output is correct
9 Correct 528 ms 76564 KB Output is correct
10 Correct 40 ms 38024 KB Output is correct
11 Correct 188 ms 56664 KB Output is correct
12 Correct 57 ms 40120 KB Output is correct
13 Correct 133 ms 49644 KB Output is correct
14 Correct 18 ms 33492 KB Output is correct
15 Correct 22 ms 33848 KB Output is correct
16 Correct 573 ms 76396 KB Output is correct
17 Correct 16 ms 33748 KB Output is correct
18 Correct 16 ms 33732 KB Output is correct
19 Correct 17 ms 33748 KB Output is correct
20 Correct 17 ms 33780 KB Output is correct
21 Correct 20 ms 33120 KB Output is correct
22 Correct 16 ms 33696 KB Output is correct
23 Correct 1298 ms 96448 KB Output is correct
24 Correct 17 ms 33748 KB Output is correct
25 Correct 24 ms 34088 KB Output is correct
26 Correct 24 ms 33860 KB Output is correct
27 Correct 25 ms 34176 KB Output is correct
28 Correct 483 ms 58616 KB Output is correct
29 Correct 745 ms 71528 KB Output is correct
30 Correct 1100 ms 83504 KB Output is correct
31 Correct 1352 ms 96472 KB Output is correct
32 Correct 15 ms 33716 KB Output is correct
33 Correct 18 ms 33748 KB Output is correct
34 Correct 16 ms 33748 KB Output is correct
35 Correct 18 ms 33128 KB Output is correct
36 Correct 17 ms 33184 KB Output is correct
37 Correct 17 ms 33748 KB Output is correct
38 Correct 16 ms 33800 KB Output is correct
39 Correct 16 ms 33692 KB Output is correct
40 Correct 17 ms 33748 KB Output is correct
41 Correct 16 ms 33108 KB Output is correct
42 Correct 16 ms 33696 KB Output is correct
43 Correct 20 ms 33748 KB Output is correct
44 Correct 23 ms 33996 KB Output is correct
45 Correct 625 ms 69008 KB Output is correct
46 Correct 1006 ms 84520 KB Output is correct
47 Correct 971 ms 84580 KB Output is correct
48 Correct 16 ms 33700 KB Output is correct
49 Correct 16 ms 33696 KB Output is correct
50 Correct 16 ms 33696 KB Output is correct
51 Correct 16 ms 33692 KB Output is correct
52 Correct 17 ms 33712 KB Output is correct
53 Correct 18 ms 33716 KB Output is correct
54 Correct 16 ms 33748 KB Output is correct
55 Runtime error 1156 ms 165404 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -