oj.uz

Submission #498297

# Submission time Handle Problem Language Result Execution time Memory
498297 2021-12-24T22:36:48 Z thomas_li Fountain Parks (IOI21_parks) C++17
0 / 100
 0 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

void build(vector<int> u,vector<int> v, vector<int> a, vector<int> b);

void mbuild(vector<int> u,vector<int> v, vector<int> a, vector<int> b){
    int m = u.size();
    for(int i = 0; i < m; i++){
        cout << u[i] << " " << v[i] << " " << a[i] << " " << b[i] << "\n";
    }
}
int construct_roads(vector<int> sus, vector<int> amongus){
    set<array<int,3>> a; set<array<int,2>> used;
    int n = sus.size();
    vector<int> par(n),sz(n,1); int cnt = n;
    for(int i = 0; i < n; i++) a.insert({sus[i],amongus[i],i}),par[i] = i;
    auto has = [&](int x, int y){
        auto itr = a.lower_bound({x,y,-1});
        if(itr == a.end()) return -1;
        return (*itr)[2];
    };
    auto find = [&](int x){
        while(x != par[x]){
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };
    auto join = [&](int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        if(sz[x] > sz[y]) swap(x,y);     
        sz[y] += sz[x];
        cnt--;
        par[x] = y;
        return true;
    };
    vector<int> u,v,ba,bb;
    auto add_sol = [&](int i, int j, int x, int y){ // connect fountain i and j with (x,y) bench
        u.emplace_back(i); v.emplace_back(j);
        used.insert({x,y});
        ba.emplace_back(x); bb.emplace_back(y);
    };
    for(auto[x,y,i] : a){
        int p;
        if((p = has(x+2,y)) != -1){
            if(find(i) != find(p)){
                if((x+y) % 4 == 0){
                    join(i,p);   
                    add_sol(i,p,x+1,y+1);
                } else if(used.find({x+1,y-1}) == used.end()){
                    join(i,p);
                    add_sol(i,p,x+1,y-1);
                }
            }  
        }
        if((p = has(x,y+2)) != -1){
            if(find(i) != find(p)){
                if((x+y) % 4 != 0){
                    join(i,p);   
                    add_sol(i,p,x+1,y+1);
                } else if(used.find({x-1,y+1}) == used.end()){
                    join(i,p);
                    add_sol(i,p,x-1,y+1);
                }
            }  
        }
    }
    if(cnt != 1) return 0;
    build(u,v,ba,bb); 
    //mbuild(u,v,ba,bb); 
    return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Pair u[0]=0 @(2, 2) and v[0]=1 @(2, 6) does not form a valid edge (distance != 2)
4 Halted 0 ms 0 KB -