oj.uz

Submission #439827

# Submission time Handle Problem Language Result Execution time Memory
439827 2021-06-30T23:20:40 Z humbertoyusta Fountain Parks (IOI21_parks) C++17
0 / 100
 326 ms 44456 KB 
#include "parks.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ii pair<int,int>
using namespace std;
#define maxn 200010
#define db(x) cerr<<#x<<": "<<(x)<<"\n";

int mx[4] = { 0 , 2 , 0 , -2 };
int my[4] = { 2 , 0 , -2 , 0 };
int vis[maxn];
ii arr[maxn];
map<ii,int> mk;
vector<int> U, V, A, B;
map<ii,int> mp;

bool add_edge(int u,int v,int plus_){
    U.push_back(u);
    V.push_back(v);
    if( arr[u].f != arr[v].f ){
        if( mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] ) return false;
        A.push_back( (arr[u].f+arr[v].f)/2 );
        B.push_back( arr[u].s + plus_ );
        mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] = true;
    }
    else{
        if( mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] ) return false;
        A.push_back( arr[u].f + plus_ );
        B.push_back( (arr[u].s+arr[v].s)/2 );
        mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] = true;
    }
    return true;
}

void dfs(int u,int p,int plus_){
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[u].f + mx[i];
        int ny = arr[u].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;

            int gp = p / 2 * 2 + ( p + 1 ) % 2;
            int nplus = plus_;
            if( i != gp ) nplus *= -1;

            if( add_edge(u,v,nplus) )
                dfs(v,i,nplus);
        }
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
//    if (x.size() == 1) {
//        vector<int> pra;
//        build(pra, pra, pra, pra);
//        return 1;
//    }

    int n = x.size();

    pair<ii,int> st = { { 2000000007 , 2000000007 } , -1 };
    for(int i=0; i<n; i++){
        arr[i] = {x[i],y[i]};
        mp[{x[i],y[i]}] = i + 1;
        st = min( st , { arr[i] , i } );
    }

    int u = st.s;
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[0].f + mx[i];
        int ny = arr[0].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;
            int plus_ = ( i == 1 ) + ( i == 2 ) - ( i == 0 ) - ( i == 3 );
            add_edge(u,v,plus_);
            dfs(v,i,plus_);
        }
    }

    for(int i=0; i<n; i++)
        if( vis[i] == 0 )
            return 0;

    build(U, V, A, B);
    return 1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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