제출 #1303234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303234		chaitanyamehta	Towers (NOI22_towers)	C++20	컴파일 에러	0 ms	0 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

struct Edge{
    int v , id;
};
const int maxn = 1e6+1;
vector<Edge> g[3*maxn];
vector<int> vis(3*maxn , 0);
vector<int> used(maxn , 0);
vector<int> par_edge(3*maxn , -1);
vector<int> deg(3*maxn , 0);

void dfs(int u){
    vis[u] = 1;
    for(auto v : g[u]){
        if(v.id == par_edge[u])continue;
        if(!vis[v.v]){
            par_edge[v.v] =  v.id;
            dfs(v.v);
        }
    }
}

void dfs2(int u){
    vis[u] =1;
    for(auto e : g[u]){
        int v = e.v;
        if(vis[v] || par_edge[v] != e.id)continue;
        dfs2(v);

        if(!used[e.id] && deg[u] < 2 && deg[v] < 2){
            used[e.id] = 1;
            deg[u]++;
            deg[v]++;
         }
    }
}


signed main(){
    int n;cin>>n;


    vector<int> x(n) , y(n);
    for(int i = 0 ; i < n; i++)cin>>x[i]>>y[i];

    vector<int> xs = x, ys = y;
    sort(xs.begin() , xs.end());
    xs.erase(unique(xs.begin() , xs.end()) , xs.end());
    sort(ys.begin() , ys.end());
    ys.erase(unique(ys.begin() , ys.end()) , ys.end());

    int nx = xs.size();
    int ny = ys.size();
    vector<int> cx(n) , cy(n);

    for(int i = 0 ; i < n ; i++){
        cx[i] = lower_bound(xs.begin() , xs.end() , x[i]) - xs.begin();
        cy[i] = lower_bound(ys.begin() , ys.end() , y[i]) - ys.begin() + nx;
    }

    int V = nx + ny;
    for(int i = 0 ;i < n; i++){
        g[cx[i]].push_back({cy[i] , i});
        g[cy[i]].push_back({cx[i] , i});
    }


    for(int i = 0 ; i < V ; i++){
        if(!vis[i])dfs(i);
    }
    for(int i = 0 ; i< n ;i++){
        int u = cx[i];
        int v = cy[i];
        if(par_edge[u]!=i && par_edge[v]!=i){
            if(deg[u] <2 && deg[v] <2){
                deg[u]++;
                deg[v]++;
                used[i] = 1;
            }
        }
    }
    vis.assign(V , 0);

    for(int i = 0 ; i < V ; i++){
        if(!vis[i]) dfs2(i);
    }

    for(int i = 0 ; i < n; i++){
        cout<<used[i];
    }
}