Submission #1177877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177877		justinlgl20	Port Facility (JOI17_port_facility)	C++20	78 / 100	551 ms	84968 KiB

port_facility

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

#define int long long

#define all(x) (x).begin(), (x).end()

template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}

void _print() {cerr << "]\n";}

template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}

#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

vector<int> adj[200005];
set<int> adj2[200005];

struct dsu{
        vector<int> p;
        dsu(int n) : p(n+3,-1) {}
        int rep(int u){
                if(p[u]<0)return u;
                return p[u]=rep(p[u]);
        }
        void merge(int a,int b){
                adj[a].push_back(b);adj[b].push_back(a);
                a=rep(a),b=rep(b);
                if(a==b)return;
                if(p[a]<p[b]) swap(a,b);
                p[b]+=p[a];
                p[a]=b;
        }
};
int col[200005];
void dfs(int u,int c){
        col[u]=c;
        int x=(c+1==3?1:c+1);
        for(int i : adj[u]){
                if(col[i]!=0){
                        assert(col[i]==x);
                } else {
                        col[i]=x;
                        dfs(i,x);
                }
        }
}

const int MOD = 1000000007;

int32_t main() {
        int n;cin>>n;
        vector<vector<int>>a(n,vector<int>());
        for(int i=0;i<n;i++){
                int b,c;cin>>b>>c;
                a[i].push_back(b);
                a[i].push_back(c);
        }
        dbg("HI");
        dsu d(2*n);
        sort(all(a));
        dbg(a);
        map<int,int> pos;
        for(int i=0;i<n;i++){
                auto inx=pos.lower_bound(a[i][0]);
                auto fin=pos.upper_bound(a[i][1]);
                if(inx!=fin and fin!=pos.begin()){
                        fin--;
                        while(inx!=pos.end()){
                                d.merge(i,(inx->s)+n);
                                d.merge(i+n,(inx->s));
                                if(inx==fin or d.rep(fin->s)==d.rep(inx->s))break;
                                inx++;
                        }
                }
                pos[a[i][1]]=i;
        }
        for(int i=0;i<n;i++){
                if(d.rep(i)==d.rep(n+i)){
                        cout<<"0\n";return 0;
                }
        }
        // i is on the same side as n+1
        int an=1;
        for(int i=0;i<n;i++){
                if(i==d.rep(i)){
                        an*=2ll;
                        an%=MOD;
                        //dfs(x, 1);
                }
        }
        cout<<an<<"\n";
        return 0;
        // each end is connected to stuff so we merge the edges
        // i is where node i is and i+n is end of i
        vector<int>ans(2*n);
        for(int i=0;i<n;i++){
                ans[a[i][0]] = col[i];
                ans[a[i][1]] = col[i];
                dbg(i, col[i], a[i]);
        }
        for(int i=0;i<2*n;i++){
                cout<<ans[i]<<"\n";
        }

}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22