oj.uz

Submission #800350

# Submission time Handle Problem Language Result Execution time Memory
800350 2023-08-01T13:36:42 Z TheSahib Fountain Parks (IOI21_parks) C++17
0 / 100
 1 ms 1460 KB 
#include "parks.h"
#include <bits/stdc++.h>

#define ll long long
#define pii pair<int, int>


using namespace std;


const int MAX = 3e5 + 5;
pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int n = 0;
int comp = 0;
int par[MAX];

int get(int node){
    if(par[node] < 0) return node;
    return par[node] = get(par[node]);
}

bool unite(int v, int u){
    v = get(v);
    u = get(u);
    if(v == u) return false;
    if(-par[v] < -par[u]) swap(v, u);
    par[v] += par[u];
    par[u] = v;
    comp--;
    return true;
}

map<pii, int> f;

int construct_roads(vector<int> x, vector<int> y) {
    memset(par, -1, sizeof(par));
    n = x.size();
    comp = n;
    for (int i = 0; i < n; i++)
    {
        f[{x[i], y[i]}] = i;
    }
    set<pii> roads;
    vector<int> v, u;
    for (int i = 0; i < n && comp > 1; i++)
    {
        for(pii d:dir){
            pii p = {x[i] + d.first * 2, y[i] + d.second * 2};
            if(f.count(p)){
                int idx = f[p];
                if(unite(i, idx)){
                    v.push_back(i);
                    u.push_back(idx);
                    roads.insert({x[i] + d.first, y[i] + d.second});
                }
            }
        }
    }
    if(comp != 1){
        return 0;
    }
    map<pii, int> mp;
    vector<pii> abc;
    for(auto& p:roads){
        for(pii d:dir){
            pii b = {p.first + d.first, p.second + d.second};
            if(f.count(b)) continue;
            mp[b]++;
        }
    }
    for(auto& p:mp){
        if(p.second == 1) {
            abc.push_back(p.first);
            roads.erase(p.first);
        }
    }
    vector<int> a, b;
    while(abc.size() && a.size() < v.size()){
        pii p = abc.back();
        mp[p]--;
        abc.pop_back();
        
        a.push_back(p.first);
        b.push_back(p.second);
        
        for(pii d:dir){
            pii b = {p.first + d.first, p.second + d.second};
            if(roads.count(b)){
                b.first += d.first;
                b.second += d.second;
                mp[b] -= 1;
                if(mp[b] == 1){
                    abc.push_back(b);
                }
                roads.erase(b);
                break;
            }
        }
    }
    if(abc.empty() && a.size() < v.size()){
        for(auto& p:mp){
            if(p.second == 0) continue;
            a.push_back(p.first.first);
            b.push_back(p.first.second);
        }
    }
    
    build(u, v, a, b);
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Incorrect 1 ms 1364 KB Tree (a[0], b[0]) = (3, 5) is not adjacent to edge between u[0]=1 @(2, 4) and v[0]=0 @(2, 2)
5 Halted 0 ms 0 KB -