oj.uz

Submission #1092350

# Submission time Handle Problem Language Result Execution time Memory
1092350 2024-09-23T20:49:02 Z TlenekWodoru Fountain Parks (IOI21_parks) C++17
55 / 100
 3500 ms 128280 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];
bool Zaj[1000009];
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 BFS()
{
    int start=0;
    Zaj[start]=1;
    deque<int>Y;
    Y.push_back(start);
    while((int)Y.size()>0)
    {
        const int v=Y[0];
        Y.pop_front();
        for(int som : D[v])
        {
            if(Zaj[som]==0)
            {
                Zaj[som]=1;
                Y.push_back(som);
                if(match[v]==-1&&match[som]==-1)
                {
                    match[v]=som;
                    match[som]=v;
                }
            }
        }
    }
}
void SKOJ()
{
    random_shuffle(g,g+N);
    for(int i=0;i<N;i++)
    {
        match[i]=-1;
        zaj[i]=0;
    }
    BFS();
    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);
        }
    }
    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);
                Polacz(u,som);
            }
        }
    }
    for(int u : U)
    {
        if(match[u]!=-1){continue;}
        Upgrade(u);
    }
}
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct
17 Correct 11 ms 28504 KB Output is correct
18 Correct 11 ms 28508 KB Output is correct
19 Correct 11 ms 28508 KB Output is correct
20 Correct 11 ms 28632 KB Output is correct
21 Correct 11 ms 28508 KB Output is correct
22 Correct 11 ms 28504 KB Output is correct
23 Correct 935 ms 128280 KB Output is correct
24 Correct 10 ms 28508 KB Output is correct
25 Correct 13 ms 29276 KB Output is correct
26 Correct 12 ms 29008 KB Output is correct
27 Correct 13 ms 29020 KB Output is correct
28 Correct 272 ms 68180 KB Output is correct
29 Correct 472 ms 87624 KB Output is correct
30 Correct 658 ms 107344 KB Output is correct
31 Correct 937 ms 127228 KB Output is correct
32 Correct 12 ms 28504 KB Output is correct
33 Correct 11 ms 28656 KB Output is correct
34 Correct 12 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28412 KB Output is correct
37 Correct 11 ms 28604 KB Output is correct
38 Correct 10 ms 28508 KB Output is correct
39 Correct 11 ms 28444 KB Output is correct
40 Correct 14 ms 28504 KB Output is correct
41 Correct 11 ms 28608 KB Output is correct
42 Correct 12 ms 28640 KB Output is correct
43 Correct 12 ms 28864 KB Output is correct
44 Correct 14 ms 28764 KB Output is correct
45 Correct 301 ms 68228 KB Output is correct
46 Correct 473 ms 86188 KB Output is correct
47 Correct 456 ms 86036 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct
17 Correct 11 ms 28504 KB Output is correct
18 Correct 11 ms 28508 KB Output is correct
19 Correct 11 ms 28508 KB Output is correct
20 Correct 11 ms 28632 KB Output is correct
21 Correct 11 ms 28508 KB Output is correct
22 Correct 11 ms 28504 KB Output is correct
23 Correct 935 ms 128280 KB Output is correct
24 Correct 10 ms 28508 KB Output is correct
25 Correct 13 ms 29276 KB Output is correct
26 Correct 12 ms 29008 KB Output is correct
27 Correct 13 ms 29020 KB Output is correct
28 Correct 272 ms 68180 KB Output is correct
29 Correct 472 ms 87624 KB Output is correct
30 Correct 658 ms 107344 KB Output is correct
31 Correct 937 ms 127228 KB Output is correct
32 Correct 12 ms 28504 KB Output is correct
33 Correct 11 ms 28656 KB Output is correct
34 Correct 12 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28412 KB Output is correct
37 Correct 11 ms 28604 KB Output is correct
38 Correct 10 ms 28508 KB Output is correct
39 Correct 11 ms 28444 KB Output is correct
40 Correct 14 ms 28504 KB Output is correct
41 Correct 11 ms 28608 KB Output is correct
42 Correct 12 ms 28640 KB Output is correct
43 Correct 12 ms 28864 KB Output is correct
44 Correct 14 ms 28764 KB Output is correct
45 Correct 301 ms 68228 KB Output is correct
46 Correct 473 ms 86188 KB Output is correct
47 Correct 456 ms 86036 KB Output is correct
48 Correct 12 ms 28504 KB Output is correct
49 Correct 11 ms 28504 KB Output is correct
50 Correct 11 ms 28508 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 10 ms 28508 KB Output is correct
53 Correct 10 ms 28516 KB Output is correct
54 Correct 10 ms 28508 KB Output is correct
55 Execution timed out 3595 ms 106980 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct
17 Correct 11 ms 28508 KB Output is correct
18 Correct 11 ms 28632 KB Output is correct
19 Correct 12 ms 28504 KB Output is correct
20 Correct 640 ms 109892 KB Output is correct
21 Correct 769 ms 102636 KB Output is correct
22 Correct 678 ms 102724 KB Output is correct
23 Correct 581 ms 107688 KB Output is correct
24 Correct 167 ms 45904 KB Output is correct
25 Correct 292 ms 52244 KB Output is correct
26 Correct 269 ms 52204 KB Output is correct
27 Correct 716 ms 116932 KB Output is correct
28 Correct 728 ms 116904 KB Output is correct
29 Correct 720 ms 116912 KB Output is correct
30 Correct 749 ms 116968 KB Output is correct
31 Correct 18 ms 28508 KB Output is correct
32 Correct 44 ms 34304 KB Output is correct
33 Correct 85 ms 37540 KB Output is correct
34 Correct 837 ms 109964 KB Output is correct
35 Correct 23 ms 29880 KB Output is correct
36 Correct 72 ms 34764 KB Output is correct
37 Correct 144 ms 41176 KB Output is correct
38 Correct 263 ms 57604 KB Output is correct
39 Correct 335 ms 68264 KB Output is correct
40 Correct 486 ms 79084 KB Output is correct
41 Correct 598 ms 90028 KB Output is correct
42 Correct 762 ms 100968 KB Output is correct
43 Correct 12 ms 28508 KB Output is correct
44 Correct 16 ms 28600 KB Output is correct
45 Correct 13 ms 28504 KB Output is correct
46 Correct 17 ms 28508 KB Output is correct
47 Correct 12 ms 28436 KB Output is correct
48 Correct 11 ms 28508 KB Output is correct
49 Correct 10 ms 28508 KB Output is correct
50 Correct 14 ms 28424 KB Output is correct
51 Correct 11 ms 28504 KB Output is correct
52 Correct 16 ms 28508 KB Output is correct
53 Correct 17 ms 28504 KB Output is correct
54 Correct 15 ms 28760 KB Output is correct
55 Correct 13 ms 28864 KB Output is correct
56 Correct 319 ms 68188 KB Output is correct
57 Correct 502 ms 86284 KB Output is correct
58 Correct 522 ms 86148 KB Output is correct
59 Correct 12 ms 28504 KB Output is correct
60 Correct 11 ms 28508 KB Output is correct
61 Correct 11 ms 28640 KB Output is correct
62 Correct 674 ms 121580 KB Output is correct
63 Correct 688 ms 121496 KB Output is correct
64 Correct 685 ms 121748 KB Output is correct
65 Correct 13 ms 29020 KB Output is correct
66 Correct 16 ms 29532 KB Output is correct
67 Correct 332 ms 66916 KB Output is correct
68 Correct 531 ms 86696 KB Output is correct
69 Correct 724 ms 105268 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct
17 Correct 743 ms 123696 KB Output is correct
18 Correct 788 ms 123308 KB Output is correct
19 Correct 779 ms 109660 KB Output is correct
20 Correct 905 ms 109020 KB Output is correct
21 Correct 677 ms 105644 KB Output is correct
22 Correct 11 ms 28508 KB Output is correct
23 Correct 92 ms 40904 KB Output is correct
24 Correct 30 ms 31168 KB Output is correct
25 Correct 98 ms 37976 KB Output is correct
26 Correct 194 ms 44628 KB Output is correct
27 Correct 373 ms 69308 KB Output is correct
28 Correct 462 ms 79704 KB Output is correct
29 Correct 620 ms 89516 KB Output is correct
30 Correct 766 ms 99500 KB Output is correct
31 Correct 967 ms 109636 KB Output is correct
32 Correct 840 ms 116832 KB Output is correct
33 Correct 691 ms 122840 KB Output is correct
34 Correct 18 ms 29272 KB Output is correct
35 Correct 18 ms 29788 KB Output is correct
36 Correct 347 ms 69436 KB Output is correct
37 Correct 534 ms 90300 KB Output is correct
38 Correct 764 ms 110508 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28508 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28620 KB Output is correct
4 Correct 10 ms 28636 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28508 KB Output is correct
8 Correct 10 ms 28636 KB Output is correct
9 Correct 298 ms 75856 KB Output is correct
10 Correct 26 ms 33616 KB Output is correct
11 Correct 116 ms 54216 KB Output is correct
12 Correct 43 ms 35924 KB Output is correct
13 Correct 36 ms 34640 KB Output is correct
14 Correct 12 ms 28588 KB Output is correct
15 Correct 13 ms 28760 KB Output is correct
16 Correct 295 ms 74428 KB Output is correct
17 Correct 11 ms 28504 KB Output is correct
18 Correct 11 ms 28508 KB Output is correct
19 Correct 11 ms 28508 KB Output is correct
20 Correct 11 ms 28632 KB Output is correct
21 Correct 11 ms 28508 KB Output is correct
22 Correct 11 ms 28504 KB Output is correct
23 Correct 935 ms 128280 KB Output is correct
24 Correct 10 ms 28508 KB Output is correct
25 Correct 13 ms 29276 KB Output is correct
26 Correct 12 ms 29008 KB Output is correct
27 Correct 13 ms 29020 KB Output is correct
28 Correct 272 ms 68180 KB Output is correct
29 Correct 472 ms 87624 KB Output is correct
30 Correct 658 ms 107344 KB Output is correct
31 Correct 937 ms 127228 KB Output is correct
32 Correct 12 ms 28504 KB Output is correct
33 Correct 11 ms 28656 KB Output is correct
34 Correct 12 ms 28508 KB Output is correct
35 Correct 12 ms 28508 KB Output is correct
36 Correct 11 ms 28412 KB Output is correct
37 Correct 11 ms 28604 KB Output is correct
38 Correct 10 ms 28508 KB Output is correct
39 Correct 11 ms 28444 KB Output is correct
40 Correct 14 ms 28504 KB Output is correct
41 Correct 11 ms 28608 KB Output is correct
42 Correct 12 ms 28640 KB Output is correct
43 Correct 12 ms 28864 KB Output is correct
44 Correct 14 ms 28764 KB Output is correct
45 Correct 301 ms 68228 KB Output is correct
46 Correct 473 ms 86188 KB Output is correct
47 Correct 456 ms 86036 KB Output is correct
48 Correct 12 ms 28504 KB Output is correct
49 Correct 11 ms 28504 KB Output is correct
50 Correct 11 ms 28508 KB Output is correct
51 Correct 11 ms 28508 KB Output is correct
52 Correct 10 ms 28508 KB Output is correct
53 Correct 10 ms 28516 KB Output is correct
54 Correct 10 ms 28508 KB Output is correct
55 Execution timed out 3595 ms 106980 KB Time limit exceeded
56 Halted 0 ms 0 KB -