oj.uz

Submission #1092257

# Submission time Handle Problem Language Result Execution time Memory
1092257 2024-09-23T16:08:36 Z TlenekWodoru Fountain Parks (IOI21_parks) C++17
55 / 100
 1203 ms 128160 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);
    bool cv=1;
    for(int som : D[v])
    {
        if(zaj[match[som]]==0&&match[som]!=v)
        {
            cv=0;
            break;
        }
    }
    if(cv)
    for(int som : D[v])
    {
        if(zaj[match[som]]==0)
        {
            Upgrade(match[som]);
            match[v]=som;
            match[som]=v;
            return;
        }
    }
    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;}
    for(int i=0;i<n;i++)
    {
        random_shuffle(Graf[i].begin(),Graf[i].end());
    }
    for(int i=0;i<N;i++)
    {
        random_shuffle(D[i].begin(),D[i].end());
    }
    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 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct
17 Correct 13 ms 30040 KB Output is correct
18 Correct 12 ms 30552 KB Output is correct
19 Correct 9 ms 30260 KB Output is correct
20 Correct 9 ms 30040 KB Output is correct
21 Correct 9 ms 30068 KB Output is correct
22 Correct 9 ms 30044 KB Output is correct
23 Correct 990 ms 127944 KB Output is correct
24 Correct 9 ms 30040 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 14 ms 30524 KB Output is correct
27 Correct 13 ms 30808 KB Output is correct
28 Correct 313 ms 69192 KB Output is correct
29 Correct 544 ms 89460 KB Output is correct
30 Correct 771 ms 107088 KB Output is correct
31 Correct 1008 ms 128160 KB Output is correct
32 Correct 9 ms 30044 KB Output is correct
33 Correct 13 ms 30236 KB Output is correct
34 Correct 10 ms 30044 KB Output is correct
35 Correct 10 ms 30096 KB Output is correct
36 Correct 11 ms 30040 KB Output is correct
37 Correct 10 ms 30184 KB Output is correct
38 Correct 10 ms 30044 KB Output is correct
39 Correct 9 ms 30096 KB Output is correct
40 Correct 9 ms 30044 KB Output is correct
41 Correct 10 ms 30044 KB Output is correct
42 Correct 10 ms 30232 KB Output is correct
43 Correct 11 ms 30300 KB Output is correct
44 Correct 13 ms 30556 KB Output is correct
45 Correct 312 ms 69040 KB Output is correct
46 Correct 517 ms 86676 KB Output is correct
47 Correct 500 ms 86412 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct
17 Correct 13 ms 30040 KB Output is correct
18 Correct 12 ms 30552 KB Output is correct
19 Correct 9 ms 30260 KB Output is correct
20 Correct 9 ms 30040 KB Output is correct
21 Correct 9 ms 30068 KB Output is correct
22 Correct 9 ms 30044 KB Output is correct
23 Correct 990 ms 127944 KB Output is correct
24 Correct 9 ms 30040 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 14 ms 30524 KB Output is correct
27 Correct 13 ms 30808 KB Output is correct
28 Correct 313 ms 69192 KB Output is correct
29 Correct 544 ms 89460 KB Output is correct
30 Correct 771 ms 107088 KB Output is correct
31 Correct 1008 ms 128160 KB Output is correct
32 Correct 9 ms 30044 KB Output is correct
33 Correct 13 ms 30236 KB Output is correct
34 Correct 10 ms 30044 KB Output is correct
35 Correct 10 ms 30096 KB Output is correct
36 Correct 11 ms 30040 KB Output is correct
37 Correct 10 ms 30184 KB Output is correct
38 Correct 10 ms 30044 KB Output is correct
39 Correct 9 ms 30096 KB Output is correct
40 Correct 9 ms 30044 KB Output is correct
41 Correct 10 ms 30044 KB Output is correct
42 Correct 10 ms 30232 KB Output is correct
43 Correct 11 ms 30300 KB Output is correct
44 Correct 13 ms 30556 KB Output is correct
45 Correct 312 ms 69040 KB Output is correct
46 Correct 517 ms 86676 KB Output is correct
47 Correct 500 ms 86412 KB Output is correct
48 Correct 10 ms 30044 KB Output is correct
49 Correct 9 ms 30264 KB Output is correct
50 Correct 11 ms 30044 KB Output is correct
51 Correct 10 ms 30044 KB Output is correct
52 Correct 10 ms 30040 KB Output is correct
53 Correct 10 ms 30216 KB Output is correct
54 Correct 11 ms 30044 KB Output is correct
55 Incorrect 1203 ms 105768 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 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct
17 Correct 10 ms 30044 KB Output is correct
18 Correct 11 ms 30044 KB Output is correct
19 Correct 10 ms 30044 KB Output is correct
20 Correct 769 ms 107364 KB Output is correct
21 Correct 761 ms 100336 KB Output is correct
22 Correct 737 ms 101188 KB Output is correct
23 Correct 623 ms 107436 KB Output is correct
24 Correct 174 ms 45648 KB Output is correct
25 Correct 310 ms 52308 KB Output is correct
26 Correct 304 ms 52236 KB Output is correct
27 Correct 767 ms 116948 KB Output is correct
28 Correct 814 ms 116940 KB Output is correct
29 Correct 811 ms 116908 KB Output is correct
30 Correct 810 ms 116972 KB Output is correct
31 Correct 11 ms 30040 KB Output is correct
32 Correct 42 ms 35724 KB Output is correct
33 Correct 80 ms 37968 KB Output is correct
34 Correct 776 ms 104920 KB Output is correct
35 Correct 19 ms 31324 KB Output is correct
36 Correct 64 ms 35920 KB Output is correct
37 Correct 129 ms 41640 KB Output is correct
38 Correct 252 ms 58296 KB Output is correct
39 Correct 370 ms 68476 KB Output is correct
40 Correct 471 ms 79020 KB Output is correct
41 Correct 610 ms 89516 KB Output is correct
42 Correct 743 ms 100012 KB Output is correct
43 Correct 11 ms 30040 KB Output is correct
44 Correct 9 ms 30044 KB Output is correct
45 Correct 10 ms 30044 KB Output is correct
46 Correct 10 ms 30040 KB Output is correct
47 Correct 10 ms 30044 KB Output is correct
48 Correct 10 ms 30044 KB Output is correct
49 Correct 14 ms 30172 KB Output is correct
50 Correct 9 ms 30044 KB Output is correct
51 Correct 10 ms 30044 KB Output is correct
52 Correct 11 ms 30044 KB Output is correct
53 Correct 9 ms 30044 KB Output is correct
54 Correct 11 ms 30300 KB Output is correct
55 Correct 11 ms 30556 KB Output is correct
56 Correct 308 ms 69052 KB Output is correct
57 Correct 455 ms 86696 KB Output is correct
58 Correct 459 ms 86528 KB Output is correct
59 Correct 9 ms 30040 KB Output is correct
60 Correct 9 ms 30044 KB Output is correct
61 Correct 9 ms 30044 KB Output is correct
62 Correct 662 ms 121512 KB Output is correct
63 Correct 697 ms 121540 KB Output is correct
64 Correct 705 ms 121776 KB Output is correct
65 Correct 13 ms 30552 KB Output is correct
66 Correct 16 ms 31068 KB Output is correct
67 Correct 306 ms 67748 KB Output is correct
68 Correct 506 ms 87164 KB Output is correct
69 Correct 697 ms 105128 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct
17 Correct 721 ms 123308 KB Output is correct
18 Correct 713 ms 122592 KB Output is correct
19 Correct 731 ms 101436 KB Output is correct
20 Correct 839 ms 110340 KB Output is correct
21 Correct 693 ms 105644 KB Output is correct
22 Correct 14 ms 30040 KB Output is correct
23 Correct 97 ms 42116 KB Output is correct
24 Correct 31 ms 32700 KB Output is correct
25 Correct 100 ms 38736 KB Output is correct
26 Correct 173 ms 44624 KB Output is correct
27 Correct 354 ms 69360 KB Output is correct
28 Correct 480 ms 79532 KB Output is correct
29 Correct 566 ms 89072 KB Output is correct
30 Correct 708 ms 98988 KB Output is correct
31 Correct 821 ms 109104 KB Output is correct
32 Correct 857 ms 116908 KB Output is correct
33 Correct 739 ms 123308 KB Output is correct
34 Correct 14 ms 30808 KB Output is correct
35 Correct 17 ms 31324 KB Output is correct
36 Correct 332 ms 70260 KB Output is correct
37 Correct 546 ms 90556 KB Output is correct
38 Correct 755 ms 110472 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 11 ms 28508 KB Output is correct
3 Correct 14 ms 28504 KB Output is correct
4 Correct 14 ms 28508 KB Output is correct
5 Correct 10 ms 28508 KB Output is correct
6 Correct 11 ms 30248 KB Output is correct
7 Correct 11 ms 28556 KB Output is correct
8 Correct 11 ms 28632 KB Output is correct
9 Correct 363 ms 75420 KB Output is correct
10 Correct 28 ms 35128 KB Output is correct
11 Correct 115 ms 54180 KB Output is correct
12 Correct 33 ms 37440 KB Output is correct
13 Correct 45 ms 36404 KB Output is correct
14 Correct 10 ms 30296 KB Output is correct
15 Correct 10 ms 30300 KB Output is correct
16 Correct 288 ms 75792 KB Output is correct
17 Correct 13 ms 30040 KB Output is correct
18 Correct 12 ms 30552 KB Output is correct
19 Correct 9 ms 30260 KB Output is correct
20 Correct 9 ms 30040 KB Output is correct
21 Correct 9 ms 30068 KB Output is correct
22 Correct 9 ms 30044 KB Output is correct
23 Correct 990 ms 127944 KB Output is correct
24 Correct 9 ms 30040 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 14 ms 30524 KB Output is correct
27 Correct 13 ms 30808 KB Output is correct
28 Correct 313 ms 69192 KB Output is correct
29 Correct 544 ms 89460 KB Output is correct
30 Correct 771 ms 107088 KB Output is correct
31 Correct 1008 ms 128160 KB Output is correct
32 Correct 9 ms 30044 KB Output is correct
33 Correct 13 ms 30236 KB Output is correct
34 Correct 10 ms 30044 KB Output is correct
35 Correct 10 ms 30096 KB Output is correct
36 Correct 11 ms 30040 KB Output is correct
37 Correct 10 ms 30184 KB Output is correct
38 Correct 10 ms 30044 KB Output is correct
39 Correct 9 ms 30096 KB Output is correct
40 Correct 9 ms 30044 KB Output is correct
41 Correct 10 ms 30044 KB Output is correct
42 Correct 10 ms 30232 KB Output is correct
43 Correct 11 ms 30300 KB Output is correct
44 Correct 13 ms 30556 KB Output is correct
45 Correct 312 ms 69040 KB Output is correct
46 Correct 517 ms 86676 KB Output is correct
47 Correct 500 ms 86412 KB Output is correct
48 Correct 10 ms 30044 KB Output is correct
49 Correct 9 ms 30264 KB Output is correct
50 Correct 11 ms 30044 KB Output is correct
51 Correct 10 ms 30044 KB Output is correct
52 Correct 10 ms 30040 KB Output is correct
53 Correct 10 ms 30216 KB Output is correct
54 Correct 11 ms 30044 KB Output is correct
55 Incorrect 1203 ms 105768 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -