oj.uz

Submission #1050860

# Submission time Handle Problem Language Result Execution time Memory
1050860 2024-08-09T15:42:51 Z amine_aroua Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 55304 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
void dfs(int i)
{
    if(vis[i])
        return;
    vis[i] = 1;
    for(auto j : adj[i])
    {
        dfs(j);
    }
}
void add_edge(int u , int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
    set<pair<int ,int>> taken;
    for(int i = 0 ; i <n ; i++)
    {
        idx[{x[i] , y[i]}] = i;
    }
    vector<pair<int ,int>> vv;
    for(int i = 0 ; i < n ; i++)
        vv.push_back({x[i] , y[i]});
    int cnt = 100;
    while(cnt--)
    {
        u.clear();
        v.clear();
        a.clear();
        b.clear();
        taken.clear();
        adj.assign(n , {});
        vis.assign(n ,0);
        shuffle(vv.begin() , vv.end() , rng);
        for(int i = 0 ; i < n ;i++)
        {
            x[i] = vv[i].first , y[i] = vv[i].second;
        }
        bool acc = 1;
        for(int i = 0 ; i < n ;i++)
        {
            if(idx.count({x[i] + 2 , y[i]}))
            {
                u.push_back(idx[{x[i] , y[i]}]);
                v.push_back(idx[{x[i] + 2 , y[i]}]);
                a.push_back(x[i] + 1);
                if(!taken.count({x[i] + 1 , y[i] - 1}))
                {
                    b.push_back(y[i] - 1);
                    taken.insert({x[i] + 1 , y[i] - 1});
                }
                else if(!taken.count({x[i] + 1 , y[i] + 1}))
                {
                    b.push_back(y[i] + 1);
                    taken.insert({x[i] + 1 , y[i] + 1});
                }
            }
            if(idx.count({x[i] , y[i] + 2}))
            {
                
                if(!taken.count({x[i] - 1 , y[i] + 1}))
                {
                    u.push_back(idx[{x[i] , y[i]}]);
                    v.push_back(idx[{x[i] , y[i] + 2}]);
                    b.push_back(y[i] + 1);
                    a.push_back(x[i] - 1);
                    taken.insert({x[i] - 1 , y[i] +1});
                }
                else if(!taken.count({x[i] + 1 , y[i] + 1}))
                {
                    u.push_back(idx[{x[i] , y[i]}]);
                    v.push_back(idx[{x[i] , y[i] + 2}]);
                    b.push_back(y[i] + 1);
                    a.push_back(x[i] + 1);
                    taken.insert({x[i] + 1 , y[i] +1});
                }
            }
        }
        for(int i = 0 ; i < (int)u.size() ; i++)
        {
            add_edge(u[i] , v[i]);
        }
        dfs(0);
        for(int i = 0 ; i < n ; i++)
        {
            if(!vis[i])
            {
                acc = 0;
                break;
            }
        }
        if(!acc)
            continue;
        build(u , v , a , b);
        return 1;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Execution timed out 3581 ms 39472 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct
17 Correct 361 ms 55304 KB Output is correct
18 Correct 374 ms 54920 KB Output is correct
19 Execution timed out 3545 ms 41816 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 146 ms 27404 KB Output is correct
10 Correct 10 ms 3160 KB Output is correct
11 Correct 70 ms 15180 KB Output is correct
12 Correct 16 ms 4700 KB Output is correct
13 Correct 3370 ms 10456 KB Output is correct
14 Correct 31 ms 604 KB Output is correct
15 Correct 68 ms 604 KB Output is correct
16 Correct 138 ms 26016 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Wrong answer detected in grader
21 Halted 0 ms 0 KB -