제출 #447686

#제출 시각아이디문제언어결과실행 시간메모리
447686Haruto810198Port Facility (JOI17_port_facility)C++17
22 / 100
4591 ms1048580 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int,int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int MAX = 1000010; int n; int in[MAX], out[MAX]; int op[2*MAX]; bool popped[MAX]; vi edge[MAX]; list<int> qu; int pa[MAX]; int dep[MAX]; int CC; int findp(int v){ if(v == pa[v]) return v; return (pa[v] = findp(pa[v])); } void uni(int u, int v){ int pu = findp(u); int pv = findp(v); if(pu == pv) return; CC--; if(dep[pu] > dep[pv]){ pa[pv] = pu; } else if(dep[pu] == dep[pv]){ pa[pv] = pu; dep[pu]++; } else{ pa[pu] = pv; } } int tag[MAX]; int vis[MAX]; int res = 1; void dfs(int v){ for(int i : edge[v]){ if(vis[i] == 0){ vis[i] = 1; tag[i] = 1 - tag[v]; dfs(i); } else{ if(tag[i] + tag[v] != 1){ res = 0; } } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; FOR(i, 1, n, 1){ cin>>in[i]>>out[i]; op[in[i]] = i; op[out[i]] = -i; } FOR(i, 1, n, 1){ pa[i] = i; dep[i] = 0; tag[i] = -1; vis[i] = 0; } CC = n; FOR(i, 1, 2*n, 1){ if(op[i] > 0){ qu.pb(op[i]); } else if(op[i] < 0){ popped[-op[i]] = 1; auto it = prev(qu.end()); for( ; *it!= -op[i]; it = prev(it)){ if(popped[*it] == 1){ qu.erase(it); } else{ edge[-op[i]].pb(*it); edge[*it].pb(-op[i]); uni(-op[i], *it); } } qu.erase(it); } } FOR(i, 1, n, 1){ /* cerr<<"edge["<<i<<"] : "; for(int j : edge[i]){ cerr<<j<<" "; } cerr<<endl; */ } FOR(i, 1, n, 1){ if(vis[i] == 0){ tag[i] = 0; dfs(i); } } FOR(i, 1, CC, 1){ res *= 2; res %= MOD; } cout<<res<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...