oj.uz

Submission #1092340

# Submission time Handle Problem Language Result Execution time Memory
1092340 2024-09-23T20:09:56 Z TlenekWodoru Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 126076 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 odl[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(v==N)
    {
        return 1;
    }
    for(int som : D[v])
    {
        if(odl[match[som]]==odl[v]+1&&DFS(match[som]))
        {
            match[v]=som;
            match[som]=v;
            return 1;
        }
    }
    odl[v]=INT_MAX;
    return 0;
}
bool BFS()
{
    queue<int>Q;
    for(int i=0;i<N;i++)
    {
        if(match[i]==N)
        {
            odl[i]=N;
            Q.push(i);
        }
        else
        {
            odl[i]=INT_MAX;
        }
    }
    odl[N]=INT_MAX;
    while((int)Q.size()>0)
    {
        const int v=Q.front();
        Q.pop();
        for(int i=0;i<(int)D[v].size();i++)
        {
            const int somsiad=D[v][i];
            if(odl[match[somsiad]]==INT_MAX)
            {
                odl[match[somsiad]]=odl[v]+1;
                Q.push(match[somsiad]);
            }
        }
    }
    return (odl[N]!=INT_MAX);
}
void SKOJ()
{
    random_shuffle(g,g+N);
    for(int i=0;i<N;i++)
    {
        match[i]=N;
    }
    while(BFS()==1)
    {
        for(int i=0;i<N;i++)
        {
            int u=g[i];
            if(match[u]==N)
            {
                DFS(u);
            }
        }
    }
}
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;
        }
    }
    zaj[v]=1;
    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(21377);
    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;
        zaj[i]=0;
    }
    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]!=N)
            {
                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]==N&&F(u)!=F(som))
            {
                U.push_back(ind);
                Polacz(u,som);
            }
        }
    }
    for(int u : U)
    {
        if(match[u]!=N){continue;}
        Upgrade(u);
    }
}
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 12 ms 28764 KB Output is correct
19 Correct 12 ms 28612 KB Output is correct
20 Correct 12 ms 28508 KB Output is correct
21 Correct 14 ms 28508 KB Output is correct
22 Correct 11 ms 28508 KB Output is correct
23 Execution timed out 3577 ms 112732 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 12 ms 28764 KB Output is correct
19 Correct 12 ms 28612 KB Output is correct
20 Correct 12 ms 28508 KB Output is correct
21 Correct 14 ms 28508 KB Output is correct
22 Correct 11 ms 28508 KB Output is correct
23 Execution timed out 3577 ms 112732 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct
17 Correct 11 ms 28508 KB Output is correct
18 Correct 11 ms 28508 KB Output is correct
19 Correct 11 ms 28448 KB Output is correct
20 Execution timed out 3553 ms 94032 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct
17 Correct 701 ms 126076 KB Output is correct
18 Correct 693 ms 125476 KB Output is correct
19 Execution timed out 3575 ms 94036 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 28504 KB Output is correct
2 Correct 10 ms 28508 KB Output is correct
3 Correct 11 ms 28452 KB Output is correct
4 Correct 17 ms 28508 KB Output is correct
5 Correct 11 ms 28508 KB Output is correct
6 Correct 10 ms 28508 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 10 ms 28624 KB Output is correct
9 Correct 277 ms 76900 KB Output is correct
10 Correct 25 ms 33624 KB Output is correct
11 Correct 108 ms 54948 KB Output is correct
12 Correct 34 ms 36136 KB Output is correct
13 Correct 35 ms 34644 KB Output is correct
14 Correct 11 ms 28508 KB Output is correct
15 Correct 12 ms 28768 KB Output is correct
16 Correct 280 ms 75636 KB Output is correct
17 Correct 14 ms 28508 KB Output is correct
18 Correct 12 ms 28764 KB Output is correct
19 Correct 12 ms 28612 KB Output is correct
20 Correct 12 ms 28508 KB Output is correct
21 Correct 14 ms 28508 KB Output is correct
22 Correct 11 ms 28508 KB Output is correct
23 Execution timed out 3577 ms 112732 KB Time limit exceeded
24 Halted 0 ms 0 KB -