oj.uz

Submission #1092221

# Submission time Handle Problem Language Result Execution time Memory
1092221 2024-09-23T15:38:42 Z TlenekWodoru Fountain Parks (IOI21_parks) C++17
55 / 100
 1006 ms 126788 KB 
#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
struct Edge
{
    int som,ind;
};
map<pair<int,int>,int>M,M2;
vector<Edge>Graf[200009];
vector<int>D[1000009];
pair<int,int>KimJest[1000009];
bool zaj[1000009];
vector<int>Sprz;
int g[1000009];
int match[1000009];
int n,m=0,k=0,N,IleVert=0;
int f[200009],ilosc[200009];
int F(int v)
{
    if(f[v]==v){return v;}
    return f[v]=F(f[v]);
}
void Polacz(int a, int b)
{
    a=F(a);
    b=F(b);
    if(a==b){return;}
    if(ilosc[a]<ilosc[b]){swap(a,b);}
    ilosc[a]+=ilosc[b];
    f[b]=a;
}
bool DFS(int v)
{
    if(zaj[v]){return 0;}
    zaj[v]=1;
    Sprz.push_back(v);
    for(int som : D[v])
    {
        if(match[som]==-1||DFS(match[som]))
        {
            match[v]=som;
            match[som]=v;
            return 1;
        }
    }
    return 0;
}
void SKOJ()
{
    random_shuffle(g,g+N);
    for(int i=0;i<N;i++)
    {
        match[i]=-1;
        zaj[i]=0;
    }
    for(int i=0;i<N;i++)
    {
        int a=g[i];
        for(int b : D[a])
        {
            if(match[a]==-1&&match[b]==-1)
            {
                match[a]=b;
                match[b]=a;
            }
        }
    }
    random_shuffle(g,g+N);
    for(int i=0;i<N;i++)
    {
        int u=g[i];
        if(match[u]==-1)
        {
            DFS(u);
        }
        for(int temp : Sprz)
        {
            zaj[temp]=0;
        }
        Sprz.clear();
    }
}
void Upgrade(int v)
{
    zaj[v]=1;
    Sprz.push_back(v);
    for(int som : D[v])
    {
        if(zaj[match[som]]==0)
        {
            Upgrade(match[som]);
            match[v]=som;
            match[som]=v;
            return;
        }
        else if(match[som]!=v)
        {
            break;
        }
    }
    for(int u : Sprz){zaj[u]=0;}
    Sprz.clear();
    match[v]=-1;
}
void CzySpojna(int v)
{
    zaj[v]=1;
    IleVert++;
    for(auto[som,ind] : Graf[v])
    {
        if(zaj[som]){continue;}
        CzySpojna(som);
    }
}
int construct_roads(vector<int>X, vector<int>Y)
{
    srand(2137);
    n=(int)X.size();
    for(int i=0;i<n;i++)
    {
        M[{X[i],Y[i]}]=i;
    }
    for(int i=0;i<n;i++)
    {
        if(M.find({X[i]-2,Y[i]})!=M.end())
        {
            Graf[i].push_back({M[{X[i]-2,Y[i]}],m});
            Graf[M[{X[i]-2,Y[i]}]].push_back({i,m});
            m++;
        }
        if(M.find({X[i],Y[i]-2})!=M.end())
        {
            Graf[i].push_back({M[{X[i],Y[i]-2}],m});
            Graf[M[{X[i],Y[i]-2}]].push_back({i,m});
            m++;
        }
    }
    CzySpojna(0);
    if(IleVert!=n){return 0;}
    vector<pair<int,int>>E(m);
    for(int i=0;i<n;i++)
    {
        for(auto[som,ind] : Graf[i])
        {
            int a=i,b=som;
            if(pair<int,int>{X[a],Y[a]}>pair<int,int>{X[b],Y[b]}){continue;}
            E[ind]={a,b};
        }
    }
    for(int i=0;i<(int)E.size();i++)
    {
        const int a=E[i].first,b=E[i].second;
        vector<pair<int,int>>Som;
        if(Y[a]+2==Y[b])
        {
            Som.push_back({X[a]-1,Y[a]+1});
            Som.push_back({X[a]+1,Y[a]+1});
        }
        else if(X[a]+2==X[b])
        {
            Som.push_back({X[a]+1,Y[a]+1});
            Som.push_back({X[a]+1,Y[a]-1});
        }
        for(pair<int,int>som : Som)
        {
            if(M2.find(som)==M2.end())
            {
                KimJest[k]=som;
                M2[som]=k++;
            }
            int u=m+M2[som];
            D[i].push_back(u);
            D[u].push_back(i);
        }
    }
    N=m+k;
    for(int i=0;i<N;i++){g[i]=i;}
    SKOJ();
for(int I=1;I<=10;I++)
{
    for(int i=0;i<n;i++)
    {
        f[i]=i;
        ilosc[i]=1;
    }
    for(int i=0;i<n;i++)
    {
        for(auto[som,ind] : Graf[i])
        {
            if(match[ind]==-1){continue;}
            Polacz(i,som);
        }
    }
    vector<int>U;
    for(int i=0;i<n;i++){g[i]=i;}
    random_shuffle(g,g+n);
    for(int i=0;i<n;i++)
    {
        const int u=g[i];
        for(auto[som,ind] : Graf[u])
        {
            if(match[ind]==-1&&F(u)!=F(som))
            {
                U.push_back(ind);
                Polacz(u,ind);
            }
        }
    }
    if(ilosc[F(0)]==n)
    {
        vector<int>O1,O2,O3,O4;
        for(int j=0;j<m;j++)
        {
            const int a=E[j].first,b=E[j].second;
            if(match[j]!=-1)
            {
                pair<int,int>xd=KimJest[match[j]-m];
                O1.push_back(a);
                O2.push_back(b);
                O3.push_back(xd.first);
                O4.push_back(xd.second);
            }
        }
        build(O1,O2,O3,O4);
        return 1;
    }
    for(int u : U)
    {
        if(match[u]!=-1){continue;}
        Upgrade(u);
    }
}
    return 0;
    if (X.size() == 1)
    {
        build({}, {}, {}, {});
        return 1;
    }
    vector<int> u, v, a, b;
    u.push_back(0);
    v.push_back(1);
    a.push_back(X[0]+1);
    b.push_back(Y[0]-1);
    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct
17 Correct 12 ms 28508 KB Output is correct
18 Correct 12 ms 28508 KB Output is correct
19 Correct 12 ms 28636 KB Output is correct
20 Correct 11 ms 28508 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28508 KB Output is correct
23 Correct 979 ms 126788 KB Output is correct
24 Correct 11 ms 28504 KB Output is correct
25 Correct 15 ms 29152 KB Output is correct
26 Correct 14 ms 29020 KB Output is correct
27 Correct 15 ms 29020 KB Output is correct
28 Correct 305 ms 67364 KB Output is correct
29 Correct 491 ms 87672 KB Output is correct
30 Correct 710 ms 107236 KB Output is correct
31 Correct 943 ms 126344 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 10 ms 28508 KB Output is correct
34 Correct 10 ms 28508 KB Output is correct
35 Correct 10 ms 28508 KB Output is correct
36 Correct 10 ms 28508 KB Output is correct
37 Correct 11 ms 28504 KB Output is correct
38 Correct 11 ms 28640 KB Output is correct
39 Correct 12 ms 28508 KB Output is correct
40 Correct 12 ms 28508 KB Output is correct
41 Correct 12 ms 28508 KB Output is correct
42 Correct 12 ms 28508 KB Output is correct
43 Correct 16 ms 28664 KB Output is correct
44 Correct 16 ms 28896 KB Output is correct
45 Correct 334 ms 68252 KB Output is correct
46 Correct 563 ms 86296 KB Output is correct
47 Correct 525 ms 86184 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct
17 Correct 12 ms 28508 KB Output is correct
18 Correct 12 ms 28508 KB Output is correct
19 Correct 12 ms 28636 KB Output is correct
20 Correct 11 ms 28508 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28508 KB Output is correct
23 Correct 979 ms 126788 KB Output is correct
24 Correct 11 ms 28504 KB Output is correct
25 Correct 15 ms 29152 KB Output is correct
26 Correct 14 ms 29020 KB Output is correct
27 Correct 15 ms 29020 KB Output is correct
28 Correct 305 ms 67364 KB Output is correct
29 Correct 491 ms 87672 KB Output is correct
30 Correct 710 ms 107236 KB Output is correct
31 Correct 943 ms 126344 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 10 ms 28508 KB Output is correct
34 Correct 10 ms 28508 KB Output is correct
35 Correct 10 ms 28508 KB Output is correct
36 Correct 10 ms 28508 KB Output is correct
37 Correct 11 ms 28504 KB Output is correct
38 Correct 11 ms 28640 KB Output is correct
39 Correct 12 ms 28508 KB Output is correct
40 Correct 12 ms 28508 KB Output is correct
41 Correct 12 ms 28508 KB Output is correct
42 Correct 12 ms 28508 KB Output is correct
43 Correct 16 ms 28664 KB Output is correct
44 Correct 16 ms 28896 KB Output is correct
45 Correct 334 ms 68252 KB Output is correct
46 Correct 563 ms 86296 KB Output is correct
47 Correct 525 ms 86184 KB Output is correct
48 Correct 11 ms 28508 KB Output is correct
49 Correct 11 ms 28652 KB Output is correct
50 Correct 11 ms 28504 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 13 ms 28508 KB Output is correct
53 Correct 12 ms 28508 KB Output is correct
54 Correct 12 ms 28508 KB Output is correct
55 Incorrect 1006 ms 118472 KB Tree (a[17], b[17]) = (474705, 445925) is not adjacent to edge between u[17]=8158 @(4, 58308) and v[17]=11 @(4, 58310)
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct
17 Correct 11 ms 28504 KB Output is correct
18 Correct 12 ms 28504 KB Output is correct
19 Correct 12 ms 28508 KB Output is correct
20 Correct 685 ms 108868 KB Output is correct
21 Correct 756 ms 101952 KB Output is correct
22 Correct 660 ms 101752 KB Output is correct
23 Correct 535 ms 107472 KB Output is correct
24 Correct 162 ms 45768 KB Output is correct
25 Correct 283 ms 52336 KB Output is correct
26 Correct 265 ms 52312 KB Output is correct
27 Correct 821 ms 116960 KB Output is correct
28 Correct 747 ms 116904 KB Output is correct
29 Correct 718 ms 116924 KB Output is correct
30 Correct 763 ms 116904 KB Output is correct
31 Correct 13 ms 28760 KB Output is correct
32 Correct 42 ms 34304 KB Output is correct
33 Correct 86 ms 37600 KB Output is correct
34 Correct 756 ms 107076 KB Output is correct
35 Correct 22 ms 29788 KB Output is correct
36 Correct 66 ms 34900 KB Output is correct
37 Correct 142 ms 41300 KB Output is correct
38 Correct 260 ms 57784 KB Output is correct
39 Correct 328 ms 68256 KB Output is correct
40 Correct 440 ms 79276 KB Output is correct
41 Correct 565 ms 90028 KB Output is correct
42 Correct 706 ms 100872 KB Output is correct
43 Correct 11 ms 28508 KB Output is correct
44 Correct 13 ms 28416 KB Output is correct
45 Correct 11 ms 28508 KB Output is correct
46 Correct 11 ms 28508 KB Output is correct
47 Correct 16 ms 28636 KB Output is correct
48 Correct 11 ms 28508 KB Output is correct
49 Correct 11 ms 28508 KB Output is correct
50 Correct 11 ms 28620 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 12 ms 28572 KB Output is correct
53 Correct 13 ms 28508 KB Output is correct
54 Correct 14 ms 28760 KB Output is correct
55 Correct 14 ms 28764 KB Output is correct
56 Correct 299 ms 68264 KB Output is correct
57 Correct 462 ms 86332 KB Output is correct
58 Correct 465 ms 85932 KB Output is correct
59 Correct 12 ms 28508 KB Output is correct
60 Correct 11 ms 28508 KB Output is correct
61 Correct 12 ms 28508 KB Output is correct
62 Correct 706 ms 121456 KB Output is correct
63 Correct 689 ms 121632 KB Output is correct
64 Correct 716 ms 121848 KB Output is correct
65 Correct 16 ms 29020 KB Output is correct
66 Correct 18 ms 29600 KB Output is correct
67 Correct 299 ms 66748 KB Output is correct
68 Correct 490 ms 86696 KB Output is correct
69 Correct 707 ms 105132 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct
17 Correct 668 ms 123744 KB Output is correct
18 Correct 665 ms 123304 KB Output is correct
19 Correct 765 ms 102192 KB Output is correct
20 Correct 817 ms 110248 KB Output is correct
21 Correct 702 ms 105488 KB Output is correct
22 Correct 11 ms 28504 KB Output is correct
23 Correct 100 ms 40748 KB Output is correct
24 Correct 33 ms 31312 KB Output is correct
25 Correct 97 ms 37968 KB Output is correct
26 Correct 181 ms 44580 KB Output is correct
27 Correct 350 ms 69144 KB Output is correct
28 Correct 453 ms 79528 KB Output is correct
29 Correct 563 ms 89412 KB Output is correct
30 Correct 665 ms 99252 KB Output is correct
31 Correct 833 ms 109740 KB Output is correct
32 Correct 848 ms 116912 KB Output is correct
33 Correct 706 ms 123168 KB Output is correct
34 Correct 16 ms 29272 KB Output is correct
35 Correct 20 ms 29784 KB Output is correct
36 Correct 345 ms 69304 KB Output is correct
37 Correct 550 ms 90128 KB Output is correct
38 Correct 783 ms 110536 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 11 ms 28508 KB Output is correct
4 Correct 12 ms 28552 KB Output is correct
5 Correct 12 ms 28504 KB Output is correct
6 Correct 12 ms 28508 KB Output is correct
7 Correct 11 ms 28636 KB Output is correct
8 Correct 11 ms 28508 KB Output is correct
9 Correct 316 ms 75708 KB Output is correct
10 Correct 28 ms 33616 KB Output is correct
11 Correct 114 ms 54224 KB Output is correct
12 Correct 39 ms 35920 KB Output is correct
13 Correct 38 ms 34712 KB Output is correct
14 Correct 11 ms 28760 KB Output is correct
15 Correct 13 ms 28680 KB Output is correct
16 Correct 303 ms 74428 KB Output is correct
17 Correct 12 ms 28508 KB Output is correct
18 Correct 12 ms 28508 KB Output is correct
19 Correct 12 ms 28636 KB Output is correct
20 Correct 11 ms 28508 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28508 KB Output is correct
23 Correct 979 ms 126788 KB Output is correct
24 Correct 11 ms 28504 KB Output is correct
25 Correct 15 ms 29152 KB Output is correct
26 Correct 14 ms 29020 KB Output is correct
27 Correct 15 ms 29020 KB Output is correct
28 Correct 305 ms 67364 KB Output is correct
29 Correct 491 ms 87672 KB Output is correct
30 Correct 710 ms 107236 KB Output is correct
31 Correct 943 ms 126344 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 10 ms 28508 KB Output is correct
34 Correct 10 ms 28508 KB Output is correct
35 Correct 10 ms 28508 KB Output is correct
36 Correct 10 ms 28508 KB Output is correct
37 Correct 11 ms 28504 KB Output is correct
38 Correct 11 ms 28640 KB Output is correct
39 Correct 12 ms 28508 KB Output is correct
40 Correct 12 ms 28508 KB Output is correct
41 Correct 12 ms 28508 KB Output is correct
42 Correct 12 ms 28508 KB Output is correct
43 Correct 16 ms 28664 KB Output is correct
44 Correct 16 ms 28896 KB Output is correct
45 Correct 334 ms 68252 KB Output is correct
46 Correct 563 ms 86296 KB Output is correct
47 Correct 525 ms 86184 KB Output is correct
48 Correct 11 ms 28508 KB Output is correct
49 Correct 11 ms 28652 KB Output is correct
50 Correct 11 ms 28504 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 13 ms 28508 KB Output is correct
53 Correct 12 ms 28508 KB Output is correct
54 Correct 12 ms 28508 KB Output is correct
55 Incorrect 1006 ms 118472 KB Tree (a[17], b[17]) = (474705, 445925) is not adjacent to edge between u[17]=8158 @(4, 58308) and v[17]=11 @(4, 58310)
56 Halted 0 ms 0 KB -