oj.uz

Submission #1092284

# Submission time Handle Problem Language Result Execution time Memory
1092284 2024-09-23T16:59:16 Z TlenekWodoru Fountain Parks (IOI21_parks) C++17
55 / 100
 3258 ms 126716 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++)
    {
        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 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++){match[i]=-1;}
for(int I=1;I<=10;I++)
{
    for(int i=0;i<N;i++){g[i]=i;}
    SKOJ();
    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);
        }
    }
    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;
    }
    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);
            }
        }
    }
    random_shuffle(U.begin(),U.end());
    for(int i=0;i<N;i++){match[i]=-1;}
    for(int u : U)
    {
        for(int som : D[u])
        {
            if(match[u]==-1&&match[som]==-1)
            {
                match[u]=som;
                match[som]=u;
            }
        }
    }
}
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct
17 Correct 13 ms 28508 KB Output is correct
18 Correct 11 ms 28500 KB Output is correct
19 Correct 11 ms 28504 KB Output is correct
20 Correct 12 ms 28636 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28588 KB Output is correct
23 Correct 1197 ms 126716 KB Output is correct
24 Correct 17 ms 28508 KB Output is correct
25 Correct 14 ms 29016 KB Output is correct
26 Correct 14 ms 29016 KB Output is correct
27 Correct 15 ms 29236 KB Output is correct
28 Correct 346 ms 67572 KB Output is correct
29 Correct 576 ms 87884 KB Output is correct
30 Correct 877 ms 107320 KB Output is correct
31 Correct 1139 ms 125764 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 11 ms 28504 KB Output is correct
34 Correct 13 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28516 KB Output is correct
37 Correct 11 ms 28508 KB Output is correct
38 Correct 14 ms 28500 KB Output is correct
39 Correct 14 ms 28544 KB Output is correct
40 Correct 10 ms 28508 KB Output is correct
41 Correct 10 ms 28468 KB Output is correct
42 Correct 10 ms 28504 KB Output is correct
43 Correct 11 ms 28764 KB Output is correct
44 Correct 12 ms 29020 KB Output is correct
45 Correct 308 ms 68420 KB Output is correct
46 Correct 499 ms 86292 KB Output is correct
47 Correct 495 ms 86184 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct
17 Correct 13 ms 28508 KB Output is correct
18 Correct 11 ms 28500 KB Output is correct
19 Correct 11 ms 28504 KB Output is correct
20 Correct 12 ms 28636 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28588 KB Output is correct
23 Correct 1197 ms 126716 KB Output is correct
24 Correct 17 ms 28508 KB Output is correct
25 Correct 14 ms 29016 KB Output is correct
26 Correct 14 ms 29016 KB Output is correct
27 Correct 15 ms 29236 KB Output is correct
28 Correct 346 ms 67572 KB Output is correct
29 Correct 576 ms 87884 KB Output is correct
30 Correct 877 ms 107320 KB Output is correct
31 Correct 1139 ms 125764 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 11 ms 28504 KB Output is correct
34 Correct 13 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28516 KB Output is correct
37 Correct 11 ms 28508 KB Output is correct
38 Correct 14 ms 28500 KB Output is correct
39 Correct 14 ms 28544 KB Output is correct
40 Correct 10 ms 28508 KB Output is correct
41 Correct 10 ms 28468 KB Output is correct
42 Correct 10 ms 28504 KB Output is correct
43 Correct 11 ms 28764 KB Output is correct
44 Correct 12 ms 29020 KB Output is correct
45 Correct 308 ms 68420 KB Output is correct
46 Correct 499 ms 86292 KB Output is correct
47 Correct 495 ms 86184 KB Output is correct
48 Correct 15 ms 28508 KB Output is correct
49 Correct 12 ms 28632 KB Output is correct
50 Correct 13 ms 28508 KB Output is correct
51 Correct 13 ms 28508 KB Output is correct
52 Correct 13 ms 28504 KB Output is correct
53 Correct 11 ms 28508 KB Output is correct
54 Correct 12 ms 28528 KB Output is correct
55 Incorrect 3258 ms 105748 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct
17 Correct 12 ms 28508 KB Output is correct
18 Correct 12 ms 28504 KB Output is correct
19 Correct 15 ms 28508 KB Output is correct
20 Correct 799 ms 108508 KB Output is correct
21 Correct 920 ms 101712 KB Output is correct
22 Correct 705 ms 101456 KB Output is correct
23 Correct 597 ms 106924 KB Output is correct
24 Correct 168 ms 45140 KB Output is correct
25 Correct 314 ms 51564 KB Output is correct
26 Correct 306 ms 51656 KB Output is correct
27 Correct 743 ms 116380 KB Output is correct
28 Correct 738 ms 116392 KB Output is correct
29 Correct 722 ms 116396 KB Output is correct
30 Correct 742 ms 116392 KB Output is correct
31 Correct 12 ms 28508 KB Output is correct
32 Correct 49 ms 34340 KB Output is correct
33 Correct 92 ms 37208 KB Output is correct
34 Correct 729 ms 106052 KB Output is correct
35 Correct 22 ms 29784 KB Output is correct
36 Correct 66 ms 34900 KB Output is correct
37 Correct 135 ms 40788 KB Output is correct
38 Correct 243 ms 57272 KB Output is correct
39 Correct 336 ms 67060 KB Output is correct
40 Correct 455 ms 77480 KB Output is correct
41 Correct 573 ms 87856 KB Output is correct
42 Correct 706 ms 98216 KB Output is correct
43 Correct 12 ms 28528 KB Output is correct
44 Correct 11 ms 28508 KB Output is correct
45 Correct 12 ms 28596 KB Output is correct
46 Correct 12 ms 28508 KB Output is correct
47 Correct 13 ms 28508 KB Output is correct
48 Correct 12 ms 28504 KB Output is correct
49 Correct 12 ms 28504 KB Output is correct
50 Correct 12 ms 28508 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 12 ms 28508 KB Output is correct
53 Correct 12 ms 28424 KB Output is correct
54 Correct 13 ms 28764 KB Output is correct
55 Correct 14 ms 28764 KB Output is correct
56 Correct 290 ms 67516 KB Output is correct
57 Correct 505 ms 85120 KB Output is correct
58 Correct 523 ms 84900 KB Output is correct
59 Correct 18 ms 28504 KB Output is correct
60 Correct 13 ms 28508 KB Output is correct
61 Correct 12 ms 28508 KB Output is correct
62 Correct 787 ms 119764 KB Output is correct
63 Correct 809 ms 119792 KB Output is correct
64 Correct 678 ms 120080 KB Output is correct
65 Correct 19 ms 29016 KB Output is correct
66 Correct 16 ms 29528 KB Output is correct
67 Correct 333 ms 65976 KB Output is correct
68 Correct 534 ms 85416 KB Output is correct
69 Correct 715 ms 103512 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct
17 Correct 776 ms 121736 KB Output is correct
18 Correct 740 ms 121000 KB Output is correct
19 Correct 758 ms 99808 KB Output is correct
20 Correct 817 ms 108716 KB Output is correct
21 Correct 682 ms 105132 KB Output is correct
22 Correct 12 ms 28504 KB Output is correct
23 Correct 95 ms 40936 KB Output is correct
24 Correct 36 ms 31316 KB Output is correct
25 Correct 102 ms 37716 KB Output is correct
26 Correct 180 ms 44112 KB Output is correct
27 Correct 360 ms 68740 KB Output is correct
28 Correct 470 ms 78928 KB Output is correct
29 Correct 592 ms 88748 KB Output is correct
30 Correct 687 ms 98480 KB Output is correct
31 Correct 845 ms 108972 KB Output is correct
32 Correct 813 ms 116296 KB Output is correct
33 Correct 713 ms 122696 KB Output is correct
34 Correct 16 ms 29272 KB Output is correct
35 Correct 19 ms 29788 KB Output is correct
36 Correct 365 ms 69472 KB Output is correct
37 Correct 519 ms 90300 KB Output is correct
38 Correct 806 ms 110412 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28508 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 12 ms 28640 KB Output is correct
4 Correct 16 ms 28504 KB Output is correct
5 Correct 12 ms 28508 KB Output is correct
6 Correct 14 ms 28596 KB Output is correct
7 Correct 14 ms 28476 KB Output is correct
8 Correct 11 ms 28504 KB Output is correct
9 Correct 333 ms 75848 KB Output is correct
10 Correct 29 ms 33624 KB Output is correct
11 Correct 115 ms 54204 KB Output is correct
12 Correct 42 ms 35900 KB Output is correct
13 Correct 37 ms 34652 KB Output is correct
14 Correct 12 ms 28764 KB Output is correct
15 Correct 12 ms 28764 KB Output is correct
16 Correct 321 ms 74380 KB Output is correct
17 Correct 13 ms 28508 KB Output is correct
18 Correct 11 ms 28500 KB Output is correct
19 Correct 11 ms 28504 KB Output is correct
20 Correct 12 ms 28636 KB Output is correct
21 Correct 12 ms 28508 KB Output is correct
22 Correct 12 ms 28588 KB Output is correct
23 Correct 1197 ms 126716 KB Output is correct
24 Correct 17 ms 28508 KB Output is correct
25 Correct 14 ms 29016 KB Output is correct
26 Correct 14 ms 29016 KB Output is correct
27 Correct 15 ms 29236 KB Output is correct
28 Correct 346 ms 67572 KB Output is correct
29 Correct 576 ms 87884 KB Output is correct
30 Correct 877 ms 107320 KB Output is correct
31 Correct 1139 ms 125764 KB Output is correct
32 Correct 11 ms 28508 KB Output is correct
33 Correct 11 ms 28504 KB Output is correct
34 Correct 13 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28516 KB Output is correct
37 Correct 11 ms 28508 KB Output is correct
38 Correct 14 ms 28500 KB Output is correct
39 Correct 14 ms 28544 KB Output is correct
40 Correct 10 ms 28508 KB Output is correct
41 Correct 10 ms 28468 KB Output is correct
42 Correct 10 ms 28504 KB Output is correct
43 Correct 11 ms 28764 KB Output is correct
44 Correct 12 ms 29020 KB Output is correct
45 Correct 308 ms 68420 KB Output is correct
46 Correct 499 ms 86292 KB Output is correct
47 Correct 495 ms 86184 KB Output is correct
48 Correct 15 ms 28508 KB Output is correct
49 Correct 12 ms 28632 KB Output is correct
50 Correct 13 ms 28508 KB Output is correct
51 Correct 13 ms 28508 KB Output is correct
52 Correct 13 ms 28504 KB Output is correct
53 Correct 11 ms 28508 KB Output is correct
54 Correct 12 ms 28528 KB Output is correct
55 Incorrect 3258 ms 105748 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -