Submission #1217241

#TimeUsernameProblemLanguageResultExecution timeMemory
1217241woatjudgePort Facility (JOI17_port_facility)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> #define int long long using namespace std; #define L(i, j, k) for(int i = (j); i <= (k); ++i) #define R(i, j, k) for(int i = (j); i >= (k); --i) std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count()); const int MOD=1e9+7; void solve() { int n;cin>>n; vector<pair<int,int>> vec(n); vector<bool> dead(n); vector<int> ev(2*n); L(i,0,n-1){ cin>>vec[i].first>>vec[i].second; vec[i].first--;vec[i].second--; ev[vec[i].first]=i; ev[vec[i].second]=i; } set<pair<int,int>> ativo; vector<vector<int>> adj(n); L(i,0,2*n-1){ if(!dead[ev[i]]){ if(!ativo.empty()){ auto pt=ativo.begin(); auto [r,id]=*pt; if(r<vec[ev[i]].second){ adj[id].push_back(ev[i]); adj[ev[i]].push_back(id); } } ativo.insert({vec[ev[i]].second,ev[i]}); dead[ev[i]]=1; } else{ ativo.erase({i,ev[i]}); } } vector<int> cor(n,-1); auto dfscor=[&](auto&& self, int node, int pai)->void{ cor[node]=cor[pai]^1; for(auto a:adj[node]){ if(a==pai)continue; self(self,a,node); } }; int cnt=0; L(i,0,n-1){ if(cor[i]==-1){ cor[i]=1; cnt++; dfscor(dfscor,i,i); } } { vector<vector<int>> st(2); L(i,0,n-1)dead[i]=0; L(i,0,2*n-1){ int id=ev[i]; if(dead[id]){ if(st[cor[id]].empty() || st[cor[id]].back()!=id){ cout<<0;return; } st[cor[id]].pop_back(); } else{ dead[id]=1; st[cor[id]].push_back(id); } } } int potat=2; int resp=1; while(cnt>0){ if(cnt%2)resp*=potat; cnt/=2; potat*=potat; resp%=MOD; potat%=MOD; } cout<<resp; return; } int32_t main() { std::cin.tie(0)->sync_with_stdio(0); std::cin.exceptions(std::cin.failbit); int T = 1; while(T--) { solve(); } 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...