# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22974 | 2017-04-30T19:09:57 Z | sbansalcs | Port Facility (JOI17_port_facility) | C++14 | 3453 ms | 992584 KB |
#include <iostream> #include <vector> #include <set> #include <assert.h> using namespace std; const int N = 2e5+5; set<int> st[N][2]; set<int> st2[N][2]; int A[N],B[N]; // pair<int,int> arr[N]; int comps; bool in[2*N]; int ver[2*N]; int rel[N]; int parent[N]; int sz[N]; set<int> ms; int vt[N]; int done[2*N]; int read() { int x;return scanf("%d",&x),x; } bool addE(int a, int b) { // cout<<"addE : "<<a<<" "<<b<<endl; int u = parent[a],v=parent[b]; // cout<<"oh : "<<u<<" "<<v<<endl; if(u==v) { return rel[a]!=rel[b]; } comps--; int d = !(rel[a]^rel[b]); if(sz[u]>sz[v]) swap(u,v); for(int i=0;i<2;i++) { for(auto c:st[u][i]) { st[v][i^d].insert(c); st2[v][i^d].insert(B[c]); parent[c]=v; rel[c]^=d; } } return 1; } int get_replacement(int x, int a) { int p = parent[x]; int d = rel[x]; set<int>::iterator it; it = st2[p][d].lower_bound(a+1); if(it!=st2[p][d].end()) return *it; return -1; } void ass(bool x) { while(!x) { } } int main() { int ss=0; int n=read(); comps=n; int dd=0; for(int i=1;i<=n;i++) { A[i]=read();B[i]=read(); in[A[i]]=1; ver[A[i]]=ver[B[i]]=i; parent[i]=i; st[i][0].insert(i); sz[i]=1; st2[i][0].insert(B[i]); } // vector<int> vt; int v; for(int i=1;i<=2*n;i++) { if(!in[i]) continue; // vt.clear(); ss=0; v = ver[i]; ass(A[v]==i); for(auto c:ms) { if(c>A[v]) break; // vt.push_back(c); vt[++ss]=c; } int c; for(int j=1;j<=ss;j++) { c= vt[j]; // assert(c<A[v]); // assert(c!=A[v]); // while(c==A[v]) { // } int h = get_replacement(ver[c],A[v]); // assert(h>A[v] || h==-1); // cout<<"erased : "<<c<<" and inserted: "<<h<<endl; ms.erase(ms.find(c)); if(h!=-1) ms.insert(h),dd++; assert(dd<=N*10); } bool f=0; ss=0; for(auto c:ms) { if(c>B[v]) break; if(!addE(v,ver[c])) { // cout<<"fuck : "<<v<<" "<<c<<" "<<ver[c]<<endl; // assert(0); cout<<0;return 0; } if(f==0) f=1; else vt[++ss]=c; } for(int j=1;j<=ss;j++) { c= vt[j]; ms.erase(ms.find(c)); } ms.insert(B[v]);dd++; assert(dd<=N*10); } // cout<<"yeah : \n"; // cout<<comps<<endl; long long ans=1;int mod=1e9+7; for(int i=1;i<=comps;i++) { ans=(ans*2)%mod; } cout<<ans; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 47728 KB | Output is correct |
2 | Correct | 6 ms | 47728 KB | Output is correct |
3 | Correct | 6 ms | 47728 KB | Output is correct |
4 | Correct | 13 ms | 47728 KB | Output is correct |
5 | Correct | 9 ms | 47728 KB | Output is correct |
6 | Correct | 9 ms | 47728 KB | Output is correct |
7 | Correct | 6 ms | 47728 KB | Output is correct |
8 | Correct | 3 ms | 47728 KB | Output is correct |
9 | Correct | 6 ms | 47728 KB | Output is correct |
10 | Correct | 3 ms | 47728 KB | Output is correct |
11 | Correct | 6 ms | 47728 KB | Output is correct |
12 | Correct | 9 ms | 47728 KB | Output is correct |
13 | Correct | 6 ms | 47728 KB | Output is correct |
14 | Correct | 6 ms | 47728 KB | Output is correct |
15 | Correct | 9 ms | 47728 KB | Output is correct |
16 | Correct | 6 ms | 47728 KB | Output is correct |
17 | Correct | 6 ms | 47728 KB | Output is correct |
18 | Correct | 9 ms | 47728 KB | Output is correct |
19 | Correct | 9 ms | 47728 KB | Output is correct |
20 | Correct | 3 ms | 47728 KB | Output is correct |
21 | Correct | 9 ms | 47728 KB | Output is correct |
22 | Correct | 9 ms | 47728 KB | Output is correct |
23 | Correct | 13 ms | 47728 KB | Output is correct |
24 | Correct | 13 ms | 47728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 47728 KB | Output is correct |
2 | Correct | 6 ms | 47728 KB | Output is correct |
3 | Correct | 6 ms | 47728 KB | Output is correct |
4 | Correct | 13 ms | 47728 KB | Output is correct |
5 | Correct | 9 ms | 47728 KB | Output is correct |
6 | Correct | 9 ms | 47728 KB | Output is correct |
7 | Correct | 6 ms | 47728 KB | Output is correct |
8 | Correct | 3 ms | 47728 KB | Output is correct |
9 | Correct | 6 ms | 47728 KB | Output is correct |
10 | Correct | 3 ms | 47728 KB | Output is correct |
11 | Correct | 6 ms | 47728 KB | Output is correct |
12 | Correct | 9 ms | 47728 KB | Output is correct |
13 | Correct | 6 ms | 47728 KB | Output is correct |
14 | Correct | 6 ms | 47728 KB | Output is correct |
15 | Correct | 9 ms | 47728 KB | Output is correct |
16 | Correct | 6 ms | 47728 KB | Output is correct |
17 | Correct | 6 ms | 47728 KB | Output is correct |
18 | Correct | 9 ms | 47728 KB | Output is correct |
19 | Correct | 9 ms | 47728 KB | Output is correct |
20 | Correct | 3 ms | 47728 KB | Output is correct |
21 | Correct | 9 ms | 47728 KB | Output is correct |
22 | Correct | 9 ms | 47728 KB | Output is correct |
23 | Correct | 13 ms | 47728 KB | Output is correct |
24 | Correct | 13 ms | 47728 KB | Output is correct |
25 | Correct | 16 ms | 48256 KB | Output is correct |
26 | Correct | 13 ms | 48256 KB | Output is correct |
27 | Correct | 16 ms | 48256 KB | Output is correct |
28 | Correct | 13 ms | 48256 KB | Output is correct |
29 | Correct | 9 ms | 48256 KB | Output is correct |
30 | Correct | 6 ms | 48256 KB | Output is correct |
31 | Correct | 9 ms | 48256 KB | Output is correct |
32 | Correct | 13 ms | 48256 KB | Output is correct |
33 | Correct | 6 ms | 48124 KB | Output is correct |
34 | Correct | 6 ms | 47992 KB | Output is correct |
35 | Correct | 9 ms | 47992 KB | Output is correct |
36 | Correct | 9 ms | 47992 KB | Output is correct |
37 | Correct | 6 ms | 47992 KB | Output is correct |
38 | Correct | 6 ms | 47992 KB | Output is correct |
39 | Correct | 13 ms | 47992 KB | Output is correct |
40 | Correct | 3 ms | 47992 KB | Output is correct |
41 | Correct | 206 ms | 94852 KB | Output is correct |
42 | Correct | 213 ms | 94852 KB | Output is correct |
43 | Correct | 6 ms | 48124 KB | Output is correct |
44 | Correct | 9 ms | 48124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 47728 KB | Output is correct |
2 | Correct | 6 ms | 47728 KB | Output is correct |
3 | Correct | 6 ms | 47728 KB | Output is correct |
4 | Correct | 13 ms | 47728 KB | Output is correct |
5 | Correct | 9 ms | 47728 KB | Output is correct |
6 | Correct | 9 ms | 47728 KB | Output is correct |
7 | Correct | 6 ms | 47728 KB | Output is correct |
8 | Correct | 3 ms | 47728 KB | Output is correct |
9 | Correct | 6 ms | 47728 KB | Output is correct |
10 | Correct | 3 ms | 47728 KB | Output is correct |
11 | Correct | 6 ms | 47728 KB | Output is correct |
12 | Correct | 9 ms | 47728 KB | Output is correct |
13 | Correct | 6 ms | 47728 KB | Output is correct |
14 | Correct | 6 ms | 47728 KB | Output is correct |
15 | Correct | 9 ms | 47728 KB | Output is correct |
16 | Correct | 6 ms | 47728 KB | Output is correct |
17 | Correct | 6 ms | 47728 KB | Output is correct |
18 | Correct | 9 ms | 47728 KB | Output is correct |
19 | Correct | 9 ms | 47728 KB | Output is correct |
20 | Correct | 3 ms | 47728 KB | Output is correct |
21 | Correct | 9 ms | 47728 KB | Output is correct |
22 | Correct | 9 ms | 47728 KB | Output is correct |
23 | Correct | 13 ms | 47728 KB | Output is correct |
24 | Correct | 13 ms | 47728 KB | Output is correct |
25 | Correct | 16 ms | 48256 KB | Output is correct |
26 | Correct | 13 ms | 48256 KB | Output is correct |
27 | Correct | 16 ms | 48256 KB | Output is correct |
28 | Correct | 13 ms | 48256 KB | Output is correct |
29 | Correct | 9 ms | 48256 KB | Output is correct |
30 | Correct | 6 ms | 48256 KB | Output is correct |
31 | Correct | 9 ms | 48256 KB | Output is correct |
32 | Correct | 13 ms | 48256 KB | Output is correct |
33 | Correct | 6 ms | 48124 KB | Output is correct |
34 | Correct | 6 ms | 47992 KB | Output is correct |
35 | Correct | 9 ms | 47992 KB | Output is correct |
36 | Correct | 9 ms | 47992 KB | Output is correct |
37 | Correct | 6 ms | 47992 KB | Output is correct |
38 | Correct | 6 ms | 47992 KB | Output is correct |
39 | Correct | 13 ms | 47992 KB | Output is correct |
40 | Correct | 3 ms | 47992 KB | Output is correct |
41 | Correct | 206 ms | 94852 KB | Output is correct |
42 | Correct | 213 ms | 94852 KB | Output is correct |
43 | Correct | 6 ms | 48124 KB | Output is correct |
44 | Correct | 9 ms | 48124 KB | Output is correct |
45 | Correct | 269 ms | 74128 KB | Output is correct |
46 | Correct | 316 ms | 75976 KB | Output is correct |
47 | Correct | 289 ms | 77428 KB | Output is correct |
48 | Correct | 269 ms | 71752 KB | Output is correct |
49 | Correct | 266 ms | 77956 KB | Output is correct |
50 | Correct | 103 ms | 61456 KB | Output is correct |
51 | Correct | 149 ms | 65548 KB | Output is correct |
52 | Correct | 119 ms | 57100 KB | Output is correct |
53 | Correct | 109 ms | 61852 KB | Output is correct |
54 | Correct | 69 ms | 57100 KB | Output is correct |
55 | Correct | 69 ms | 57100 KB | Output is correct |
56 | Correct | 76 ms | 57100 KB | Output is correct |
57 | Correct | 139 ms | 61852 KB | Output is correct |
58 | Correct | 116 ms | 57100 KB | Output is correct |
59 | Correct | 143 ms | 59080 KB | Output is correct |
60 | Correct | 169 ms | 62908 KB | Output is correct |
61 | Correct | 206 ms | 68320 KB | Output is correct |
62 | Correct | 79 ms | 57100 KB | Output is correct |
63 | Correct | 59 ms | 57100 KB | Output is correct |
64 | Correct | 63 ms | 57232 KB | Output is correct |
65 | Correct | 86 ms | 57100 KB | Output is correct |
66 | Correct | 69 ms | 57100 KB | Output is correct |
67 | Runtime error | 3453 ms | 992584 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
68 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 47728 KB | Output is correct |
2 | Correct | 6 ms | 47728 KB | Output is correct |
3 | Correct | 6 ms | 47728 KB | Output is correct |
4 | Correct | 13 ms | 47728 KB | Output is correct |
5 | Correct | 9 ms | 47728 KB | Output is correct |
6 | Correct | 9 ms | 47728 KB | Output is correct |
7 | Correct | 6 ms | 47728 KB | Output is correct |
8 | Correct | 3 ms | 47728 KB | Output is correct |
9 | Correct | 6 ms | 47728 KB | Output is correct |
10 | Correct | 3 ms | 47728 KB | Output is correct |
11 | Correct | 6 ms | 47728 KB | Output is correct |
12 | Correct | 9 ms | 47728 KB | Output is correct |
13 | Correct | 6 ms | 47728 KB | Output is correct |
14 | Correct | 6 ms | 47728 KB | Output is correct |
15 | Correct | 9 ms | 47728 KB | Output is correct |
16 | Correct | 6 ms | 47728 KB | Output is correct |
17 | Correct | 6 ms | 47728 KB | Output is correct |
18 | Correct | 9 ms | 47728 KB | Output is correct |
19 | Correct | 9 ms | 47728 KB | Output is correct |
20 | Correct | 3 ms | 47728 KB | Output is correct |
21 | Correct | 9 ms | 47728 KB | Output is correct |
22 | Correct | 9 ms | 47728 KB | Output is correct |
23 | Correct | 13 ms | 47728 KB | Output is correct |
24 | Correct | 13 ms | 47728 KB | Output is correct |
25 | Correct | 16 ms | 48256 KB | Output is correct |
26 | Correct | 13 ms | 48256 KB | Output is correct |
27 | Correct | 16 ms | 48256 KB | Output is correct |
28 | Correct | 13 ms | 48256 KB | Output is correct |
29 | Correct | 9 ms | 48256 KB | Output is correct |
30 | Correct | 6 ms | 48256 KB | Output is correct |
31 | Correct | 9 ms | 48256 KB | Output is correct |
32 | Correct | 13 ms | 48256 KB | Output is correct |
33 | Correct | 6 ms | 48124 KB | Output is correct |
34 | Correct | 6 ms | 47992 KB | Output is correct |
35 | Correct | 9 ms | 47992 KB | Output is correct |
36 | Correct | 9 ms | 47992 KB | Output is correct |
37 | Correct | 6 ms | 47992 KB | Output is correct |
38 | Correct | 6 ms | 47992 KB | Output is correct |
39 | Correct | 13 ms | 47992 KB | Output is correct |
40 | Correct | 3 ms | 47992 KB | Output is correct |
41 | Correct | 206 ms | 94852 KB | Output is correct |
42 | Correct | 213 ms | 94852 KB | Output is correct |
43 | Correct | 6 ms | 48124 KB | Output is correct |
44 | Correct | 9 ms | 48124 KB | Output is correct |
45 | Correct | 269 ms | 74128 KB | Output is correct |
46 | Correct | 316 ms | 75976 KB | Output is correct |
47 | Correct | 289 ms | 77428 KB | Output is correct |
48 | Correct | 269 ms | 71752 KB | Output is correct |
49 | Correct | 266 ms | 77956 KB | Output is correct |
50 | Correct | 103 ms | 61456 KB | Output is correct |
51 | Correct | 149 ms | 65548 KB | Output is correct |
52 | Correct | 119 ms | 57100 KB | Output is correct |
53 | Correct | 109 ms | 61852 KB | Output is correct |
54 | Correct | 69 ms | 57100 KB | Output is correct |
55 | Correct | 69 ms | 57100 KB | Output is correct |
56 | Correct | 76 ms | 57100 KB | Output is correct |
57 | Correct | 139 ms | 61852 KB | Output is correct |
58 | Correct | 116 ms | 57100 KB | Output is correct |
59 | Correct | 143 ms | 59080 KB | Output is correct |
60 | Correct | 169 ms | 62908 KB | Output is correct |
61 | Correct | 206 ms | 68320 KB | Output is correct |
62 | Correct | 79 ms | 57100 KB | Output is correct |
63 | Correct | 59 ms | 57100 KB | Output is correct |
64 | Correct | 63 ms | 57232 KB | Output is correct |
65 | Correct | 86 ms | 57100 KB | Output is correct |
66 | Correct | 69 ms | 57100 KB | Output is correct |
67 | Runtime error | 3453 ms | 992584 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
68 | Halted | 0 ms | 0 KB | - |