oj.uz

답안 #1092238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092238 2024-09-23T15:52:08 Z TlenekWodoru 분수 공원 (IOI21_parks) C++17
55 / 100
 1099 ms 126644 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,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;
    }
    cout<<6/0<<endl;
    for(int u : U)
    {
        if(match[u]!=-1){continue;}
        Upgrade(u);
    }
}
    return 0;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:227:12: warning: division by zero [-Wdiv-by-zero]
  227 |     cout<<6/0<<endl;
      |           ~^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct
17 Correct 10 ms 30044 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 9 ms 30044 KB Output is correct
20 Correct 9 ms 30044 KB Output is correct
21 Correct 11 ms 30260 KB Output is correct
22 Correct 10 ms 30040 KB Output is correct
23 Correct 1027 ms 126644 KB Output is correct
24 Correct 10 ms 30044 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 11 ms 30552 KB Output is correct
27 Correct 13 ms 30652 KB Output is correct
28 Correct 289 ms 68436 KB Output is correct
29 Correct 541 ms 90956 KB Output is correct
30 Correct 853 ms 107596 KB Output is correct
31 Correct 1099 ms 126312 KB Output is correct
32 Correct 8 ms 30040 KB Output is correct
33 Correct 8 ms 30044 KB Output is correct
34 Correct 8 ms 30044 KB Output is correct
35 Correct 8 ms 30044 KB Output is correct
36 Correct 8 ms 30044 KB Output is correct
37 Correct 9 ms 30044 KB Output is correct
38 Correct 8 ms 30044 KB Output is correct
39 Correct 9 ms 30148 KB Output is correct
40 Correct 8 ms 30040 KB Output is correct
41 Correct 8 ms 30044 KB Output is correct
42 Correct 9 ms 30044 KB Output is correct
43 Correct 9 ms 30280 KB Output is correct
44 Correct 11 ms 30552 KB Output is correct
45 Correct 283 ms 69152 KB Output is correct
46 Correct 450 ms 86720 KB Output is correct
47 Correct 438 ms 86560 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct
17 Correct 10 ms 30044 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 9 ms 30044 KB Output is correct
20 Correct 9 ms 30044 KB Output is correct
21 Correct 11 ms 30260 KB Output is correct
22 Correct 10 ms 30040 KB Output is correct
23 Correct 1027 ms 126644 KB Output is correct
24 Correct 10 ms 30044 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 11 ms 30552 KB Output is correct
27 Correct 13 ms 30652 KB Output is correct
28 Correct 289 ms 68436 KB Output is correct
29 Correct 541 ms 90956 KB Output is correct
30 Correct 853 ms 107596 KB Output is correct
31 Correct 1099 ms 126312 KB Output is correct
32 Correct 8 ms 30040 KB Output is correct
33 Correct 8 ms 30044 KB Output is correct
34 Correct 8 ms 30044 KB Output is correct
35 Correct 8 ms 30044 KB Output is correct
36 Correct 8 ms 30044 KB Output is correct
37 Correct 9 ms 30044 KB Output is correct
38 Correct 8 ms 30044 KB Output is correct
39 Correct 9 ms 30148 KB Output is correct
40 Correct 8 ms 30040 KB Output is correct
41 Correct 8 ms 30044 KB Output is correct
42 Correct 9 ms 30044 KB Output is correct
43 Correct 9 ms 30280 KB Output is correct
44 Correct 11 ms 30552 KB Output is correct
45 Correct 283 ms 69152 KB Output is correct
46 Correct 450 ms 86720 KB Output is correct
47 Correct 438 ms 86560 KB Output is correct
48 Correct 9 ms 30040 KB Output is correct
49 Correct 8 ms 30044 KB Output is correct
50 Correct 9 ms 30040 KB Output is correct
51 Correct 10 ms 30044 KB Output is correct
52 Correct 8 ms 30044 KB Output is correct
53 Correct 8 ms 30256 KB Output is correct
54 Correct 8 ms 30040 KB Output is correct
55 Incorrect 956 ms 118432 KB Given structure is not connected: There is no path between vertices 0 and 3236
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct
17 Correct 8 ms 30044 KB Output is correct
18 Correct 8 ms 30040 KB Output is correct
19 Correct 8 ms 30044 KB Output is correct
20 Correct 657 ms 108104 KB Output is correct
21 Correct 746 ms 101444 KB Output is correct
22 Correct 674 ms 100996 KB Output is correct
23 Correct 582 ms 107300 KB Output is correct
24 Correct 165 ms 45904 KB Output is correct
25 Correct 273 ms 52244 KB Output is correct
26 Correct 259 ms 52220 KB Output is correct
27 Correct 730 ms 117020 KB Output is correct
28 Correct 725 ms 116968 KB Output is correct
29 Correct 712 ms 117044 KB Output is correct
30 Correct 694 ms 116908 KB Output is correct
31 Correct 8 ms 30044 KB Output is correct
32 Correct 40 ms 35724 KB Output is correct
33 Correct 79 ms 37972 KB Output is correct
34 Correct 718 ms 106312 KB Output is correct
35 Correct 16 ms 31324 KB Output is correct
36 Correct 61 ms 35920 KB Output is correct
37 Correct 129 ms 41552 KB Output is correct
38 Correct 243 ms 58296 KB Output is correct
39 Correct 321 ms 68560 KB Output is correct
40 Correct 406 ms 79112 KB Output is correct
41 Correct 540 ms 89516 KB Output is correct
42 Correct 700 ms 100008 KB Output is correct
43 Correct 8 ms 30040 KB Output is correct
44 Correct 9 ms 30044 KB Output is correct
45 Correct 8 ms 30040 KB Output is correct
46 Correct 9 ms 30144 KB Output is correct
47 Correct 9 ms 30044 KB Output is correct
48 Correct 9 ms 30128 KB Output is correct
49 Correct 9 ms 30044 KB Output is correct
50 Correct 9 ms 30240 KB Output is correct
51 Correct 9 ms 30044 KB Output is correct
52 Correct 9 ms 30184 KB Output is correct
53 Correct 8 ms 30212 KB Output is correct
54 Correct 10 ms 30300 KB Output is correct
55 Correct 13 ms 30556 KB Output is correct
56 Correct 281 ms 69088 KB Output is correct
57 Correct 458 ms 86700 KB Output is correct
58 Correct 466 ms 86552 KB Output is correct
59 Correct 9 ms 30040 KB Output is correct
60 Correct 8 ms 30044 KB Output is correct
61 Correct 8 ms 30044 KB Output is correct
62 Correct 657 ms 121516 KB Output is correct
63 Correct 691 ms 121516 KB Output is correct
64 Correct 677 ms 121772 KB Output is correct
65 Correct 11 ms 30552 KB Output is correct
66 Correct 16 ms 31068 KB Output is correct
67 Correct 288 ms 67516 KB Output is correct
68 Correct 462 ms 87216 KB Output is correct
69 Correct 665 ms 105132 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct
17 Correct 707 ms 123300 KB Output is correct
18 Correct 713 ms 122708 KB Output is correct
19 Correct 686 ms 101436 KB Output is correct
20 Correct 798 ms 110252 KB Output is correct
21 Correct 655 ms 105700 KB Output is correct
22 Correct 9 ms 30044 KB Output is correct
23 Correct 94 ms 41932 KB Output is correct
24 Correct 29 ms 32604 KB Output is correct
25 Correct 94 ms 38736 KB Output is correct
26 Correct 165 ms 44624 KB Output is correct
27 Correct 331 ms 69564 KB Output is correct
28 Correct 439 ms 79532 KB Output is correct
29 Correct 565 ms 89000 KB Output is correct
30 Correct 667 ms 98988 KB Output is correct
31 Correct 826 ms 108708 KB Output is correct
32 Correct 807 ms 116904 KB Output is correct
33 Correct 663 ms 123304 KB Output is correct
34 Correct 12 ms 30812 KB Output is correct
35 Correct 15 ms 31324 KB Output is correct
36 Correct 304 ms 70308 KB Output is correct
37 Correct 516 ms 90540 KB Output is correct
38 Correct 737 ms 110508 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30296 KB Output is correct
2 Correct 9 ms 30036 KB Output is correct
3 Correct 9 ms 30076 KB Output is correct
4 Correct 9 ms 30044 KB Output is correct
5 Correct 9 ms 30132 KB Output is correct
6 Correct 10 ms 30040 KB Output is correct
7 Correct 10 ms 30020 KB Output is correct
8 Correct 9 ms 30244 KB Output is correct
9 Correct 285 ms 76476 KB Output is correct
10 Correct 24 ms 35156 KB Output is correct
11 Correct 110 ms 55252 KB Output is correct
12 Correct 33 ms 37508 KB Output is correct
13 Correct 34 ms 35920 KB Output is correct
14 Correct 10 ms 30300 KB Output is correct
15 Correct 10 ms 30320 KB Output is correct
16 Correct 284 ms 75268 KB Output is correct
17 Correct 10 ms 30044 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 9 ms 30044 KB Output is correct
20 Correct 9 ms 30044 KB Output is correct
21 Correct 11 ms 30260 KB Output is correct
22 Correct 10 ms 30040 KB Output is correct
23 Correct 1027 ms 126644 KB Output is correct
24 Correct 10 ms 30044 KB Output is correct
25 Correct 12 ms 30812 KB Output is correct
26 Correct 11 ms 30552 KB Output is correct
27 Correct 13 ms 30652 KB Output is correct
28 Correct 289 ms 68436 KB Output is correct
29 Correct 541 ms 90956 KB Output is correct
30 Correct 853 ms 107596 KB Output is correct
31 Correct 1099 ms 126312 KB Output is correct
32 Correct 8 ms 30040 KB Output is correct
33 Correct 8 ms 30044 KB Output is correct
34 Correct 8 ms 30044 KB Output is correct
35 Correct 8 ms 30044 KB Output is correct
36 Correct 8 ms 30044 KB Output is correct
37 Correct 9 ms 30044 KB Output is correct
38 Correct 8 ms 30044 KB Output is correct
39 Correct 9 ms 30148 KB Output is correct
40 Correct 8 ms 30040 KB Output is correct
41 Correct 8 ms 30044 KB Output is correct
42 Correct 9 ms 30044 KB Output is correct
43 Correct 9 ms 30280 KB Output is correct
44 Correct 11 ms 30552 KB Output is correct
45 Correct 283 ms 69152 KB Output is correct
46 Correct 450 ms 86720 KB Output is correct
47 Correct 438 ms 86560 KB Output is correct
48 Correct 9 ms 30040 KB Output is correct
49 Correct 8 ms 30044 KB Output is correct
50 Correct 9 ms 30040 KB Output is correct
51 Correct 10 ms 30044 KB Output is correct
52 Correct 8 ms 30044 KB Output is correct
53 Correct 8 ms 30256 KB Output is correct
54 Correct 8 ms 30040 KB Output is correct
55 Incorrect 956 ms 118432 KB Given structure is not connected: There is no path between vertices 0 and 3236
56 Halted 0 ms 0 KB -