제출 #1236436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236436		AlperenT_	Fountain Parks (IOI21_parks)	C++20	55 / 100	1568 ms	153216 KiB

parks

#include <bits/stdc++.h> 
#include "parks.h"
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 1e6  + 10 , inf = 1e9+ 10 , mod = 998244353;

map <pii ,int> mp ;
map <int ,pii> mp2 ;
int cnt , dx[] = {2,-2, 0 , 0} , dy[] = {0 , 0 ,2 ,-2}  ; 

void add(int x, int y){
    if(mp[{x,y}] == 0){
        mp[{x,y}] = cnt ;
        mp2[cnt] = {x,y} ;
        cnt++;
    }
}
int par[maxn] , d[maxn] , mark[maxn] , mc[maxn];
vector <int> G[maxn] ;
int find(int v){
    if(par[v] == 0)return v;
    return par[v] = find(par[v]) ;
}
void addedge(int v ,int u){
    G[v].pb(u);
    G[u].pb(v);
    d[v]++;
    d[u]++;
}
void dfs(int v , int d =0 ){
    mark[v] =1 ;
    for(int u : G[v]){
        if(mark[u] == 1)continue ;
        if(d==0)mc[v] = u ;
        dfs(u , d^1) ;
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y){
    cnt =sz(x) +1 ; 
    vector <pii> vec ;
    rep(i , 1, sz(x)){
        mp[{x[i-1],y[i-1]}] = i ;
    }
    vector <pii> ed ; 
    rep(i , 0 , sz(x)-1){
        rep(j , 0 , 3){
            int a = x[i] + dx[j] , b = y[i] + dy[j] ;
            if(mp[{a,b}] ==0)continue ; 
            ed.pb({mp[{x[i],y[i]}]  , mp[{a,b}]}) ;
            if(j <= 1){
                add((a+x[i])/2 , b-1);
                add((a+x[i])/2 , b+1);  
            }else{
                add(a-1 , (b+y[i])/2);
                add(a+1 , (b+y[i])/2); 
            }
        }
    }
    int ted= 0;
    vector <int> V,U ; 
    rep(i ,0 , sz(ed)-1){
        int v = ed[i].F, u = ed[i].S ;
        if(find(v)==find(u))continue ; 
        if(x[v-1] == x[u-1]){
            addedge(mp[{x[v-1]-1 , (y[v-1]+y[u-1])/2}] , ted) ;
            addedge(mp[{x[v-1]+1 , (y[v-1]+y[u-1])/2}] , ted) ;
        }else{
            addedge(mp[{(x[v-1]+x[u-1])/2, y[v-1]-1}] , ted) ;
            addedge(mp[{(x[v-1]+x[u-1])/2, y[v-1]+1}] , ted) ;
        }
        par[find(v)] = find(u) ;
        V.pb(v-1);
        U.pb(u-1);
        ted++;
    }
    if(ted != sz(x)-1){
        return 0 ;
    }
    queue <int> q ;
    rep(i , ted ,cnt){
        if(d[i] == 1){
            q.push(i) ; 
        }
    }
    while(sz(q)){
        int v =q.front() ;q.pop() ;
        if(mark[v] == 1)continue ;
        mark[v] =1 ;
        int x= -1 ;
        for(int u : G[v]){
            if(mark[u] == 1)continue ;
            x = u ;
        }
        if(x==-1)continue ;
        mark[x] =1 ;
        mc[x] = v ;
        for(int w : G[x]){
            if(d[w] ==2){
                q.push(w);
            }
            d[w]-- ;
        }
    }
    int o =0 ;
    rep(i , 0 ,ted-1){
        if(mark[i] == 0){
            o++;
            if(d[i] != 2)return 0 ;
        }
    }
    rep(i , ted , cnt){
        if(sz(G[i]) && mark[i] == 0){
            o--;
        }
    }
    if(o != 0){
        return 0 ;
    }
    rep(i , 0 , ted-1){
        if(mark[i] == 1)continue ; 
        dfs(i) ;
    }
    vector <int> A,B ;
    rep(i ,0 ,ted-1){
        A.pb(mp2[mc[i]].F);
        B.pb(mp2[mc[i]].S); 
    }
    build(V,U,A,B);
    return 1; 
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30