Submission #244357

#TimeUsernameProblemLanguageResultExecution timeMemory
244357Osama_AlkhodairyPort Facility (JOI17_port_facility)C++17
0 / 100
21 ms27776 KiB
#include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long const int N = 1000001; int n, vis[N], p[N], mod = 1e9 + 7; vector <pair <int, int> > a; vector <int> f, v[N]; int find(int x){ if(p[x] == x) return x; return p[x] = find(p[x]); } void merge(int x, int y){ x = find(x); y = find(y); if(x == y){ if(vis[x] == vis[y]){ cout << 0 << endl; exit(0); } return; } p[y] = x; if(vis[x] == -1 && vis[y] == -1){ v[x].push_back(y); v[y].push_back(x); vis[x] = 0; vis[y] = 1; return; } if(vis[y] == -1) swap(x, y); if(vis[x] == -1){ v[x].push_back(y); v[y].push_back(x); vis[x] = vis[y] ^ 1; return; } if(vis[x] == (vis[y] ^ 1)){ v[x].push_back(y); v[y].push_back(x); return; } y = v[y][0]; assert(vis[x] == vis[y]); v[x].push_back(y); v[y].push_back(x); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); memset(vis, -1, sizeof vis); cin >> n; a.resize(n); f.resize(2 * n); for(int i = 0 ; i < n ; i++){ cin >> a[i].first >> a[i].second; a[i].first--; a[i].second--; f[a[i].first] = f[a[i].second] = i; p[i] = i; } vector <int> o, del(n); for(int i = 0 ; i < 2 * n ; i++){ while(o.size() && del[o.back()]){ o.pop_back(); } if(a[f[i]].first == i){ o.push_back(f[i]); } else{ del[f[i]] = 1; int j = (int)o.size() - 1; while(o[j] != f[i]){ merge(f[i], o[j]); j--; } } } int ans = 1; for(int i = 0 ; i < n ; i++){ if(find(i) == i){ ans *= 2; if(ans >= mod) ans -= mod; } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...