oj.uz

Submission #1050788

# Submission time Handle Problem Language Result Execution time Memory
1050788 2024-08-09T14:31:22 Z amine_aroua Fountain Parks (IOI21_parks) C++17
5 / 100
 354 ms 50440 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
const int MAX_X = 200000;
void dfs(int i)
{
    if(vis[i])
        return;
    vis[i] = 1;
    for(auto j : adj[i])
    {
        dfs(j);
    }
}
int mn , mx , cur_x;
void dfs_comp(int i , vector<int> &y)
{
    if(vis[i])
        return ;
    vis[i] = 1;
    mn = min(mn , y[i]);
    mx = max(mx , y[i]);
    for(auto j : adj[i])
    {
        dfs_comp(j , y);
    }
}
void add_edge(int u , int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n= (int)x.size();
    adj.assign(n , {});
    vis.assign(n , 0);
    vector<int> u , v , a , b;
    map<pair<int, int> , int> idx;
    
    for(int i = 0 ; i <n ; i++)
    {
        idx[{x[i] , y[i]}] = i;
    }
    for(int i = 0 ; i < n ;i++)
    {
        if(idx.count({x[i] , y[i] + 2}))
        {
            u.push_back(i);
            v.push_back(idx[{x[i] , y[i] + 2}]);
            add_edge(u.back() , v.back());
            b.push_back(y[i] + 1);
            a.push_back(x[i] - 1);
        }
    }
    vector<vector<int>> comp(MAX_X + 1);
    for(int i = 0 ; i < n ;i++)
    {
        if(vis[i])
            continue;
        cur_x = x[i];
        mn = 1e9;
        mx = -1e9;
        dfs_comp(i , y);
        comp[cur_x].push_back(mn);
        comp[cur_x].push_back(mx);
    }
    for(int i = 2  ;i <= MAX_X ; i+=2)
    {
        sort(comp[i].begin() , comp[i].end());
    }
    for(int i = 4 ; i <= MAX_X ; i+=2)
    {
        assert(comp[i].size() % 2 == 0);
        for(int j = 0 ; j < (int)comp[i].size() ; j++)
        {
            if(j > 0 && comp[i][j] == comp[i][j - 1])
                continue;
            int val = comp[i][j];
            if(idx.count({i - 2  ,val}))
            {
                u.push_back(idx[{i,val}]);
                v.push_back(idx[{i - 2 , val}]);
                add_edge(u.back() , v.back());
                a.push_back(i - 1);
                if(j % 2 == 0)
                    b.push_back(val - 1);
                else
                    b.push_back(val + 1);
            }
        }
    }
    vis.assign(n , 0);
    dfs(0);
    for(int i = 0 ; i < n ; i++)
    {
        if(!vis[i])
        {
            return 0;
        }
    }
    build(u , v , a , b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct
17 Correct 3 ms 4952 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5208 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 289 ms 47256 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 5 ms 5208 KB Output is correct
26 Correct 4 ms 5468 KB Output is correct
27 Correct 6 ms 5724 KB Output is correct
28 Correct 95 ms 21876 KB Output is correct
29 Correct 176 ms 30392 KB Output is correct
30 Correct 233 ms 38820 KB Output is correct
31 Correct 323 ms 47272 KB Output is correct
32 Correct 2 ms 4952 KB Output is correct
33 Correct 2 ms 4952 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 1 ms 4956 KB Output is correct
42 Correct 2 ms 4952 KB Output is correct
43 Correct 3 ms 5212 KB Output is correct
44 Correct 3 ms 5468 KB Output is correct
45 Incorrect 108 ms 21624 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct
17 Correct 3 ms 4952 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5208 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 289 ms 47256 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 5 ms 5208 KB Output is correct
26 Correct 4 ms 5468 KB Output is correct
27 Correct 6 ms 5724 KB Output is correct
28 Correct 95 ms 21876 KB Output is correct
29 Correct 176 ms 30392 KB Output is correct
30 Correct 233 ms 38820 KB Output is correct
31 Correct 323 ms 47272 KB Output is correct
32 Correct 2 ms 4952 KB Output is correct
33 Correct 2 ms 4952 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 1 ms 4956 KB Output is correct
42 Correct 2 ms 4952 KB Output is correct
43 Correct 3 ms 5212 KB Output is correct
44 Correct 3 ms 5468 KB Output is correct
45 Incorrect 108 ms 21624 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct
17 Correct 2 ms 4952 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 1 ms 4956 KB Output is correct
20 Correct 295 ms 50440 KB Output is correct
21 Correct 309 ms 47664 KB Output is correct
22 Correct 307 ms 46756 KB Output is correct
23 Correct 261 ms 40872 KB Output is correct
24 Correct 144 ms 27212 KB Output is correct
25 Correct 225 ms 36452 KB Output is correct
26 Correct 247 ms 34712 KB Output is correct
27 Correct 337 ms 41128 KB Output is correct
28 Correct 354 ms 41380 KB Output is correct
29 Correct 275 ms 43308 KB Output is correct
30 Incorrect 248 ms 36896 KB Solution announced impossible, but it is possible.
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct
17 Correct 320 ms 48808 KB Output is correct
18 Correct 318 ms 48296 KB Output is correct
19 Incorrect 299 ms 42608 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 122 ms 25792 KB Output is correct
10 Correct 8 ms 7260 KB Output is correct
11 Correct 38 ms 16324 KB Output is correct
12 Correct 9 ms 8280 KB Output is correct
13 Correct 21 ms 12636 KB Output is correct
14 Correct 2 ms 5208 KB Output is correct
15 Correct 2 ms 5212 KB Output is correct
16 Correct 122 ms 24640 KB Output is correct
17 Correct 3 ms 4952 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5208 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 289 ms 47256 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 5 ms 5208 KB Output is correct
26 Correct 4 ms 5468 KB Output is correct
27 Correct 6 ms 5724 KB Output is correct
28 Correct 95 ms 21876 KB Output is correct
29 Correct 176 ms 30392 KB Output is correct
30 Correct 233 ms 38820 KB Output is correct
31 Correct 323 ms 47272 KB Output is correct
32 Correct 2 ms 4952 KB Output is correct
33 Correct 2 ms 4952 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct
35 Correct 2 ms 4956 KB Output is correct
36 Correct 2 ms 4956 KB Output is correct
37 Correct 2 ms 4956 KB Output is correct
38 Correct 2 ms 4956 KB Output is correct
39 Correct 2 ms 4956 KB Output is correct
40 Correct 2 ms 4956 KB Output is correct
41 Correct 1 ms 4956 KB Output is correct
42 Correct 2 ms 4952 KB Output is correct
43 Correct 3 ms 5212 KB Output is correct
44 Correct 3 ms 5468 KB Output is correct
45 Incorrect 108 ms 21624 KB Solution announced impossible, but it is possible.
46 Halted 0 ms 0 KB -