# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22971 | 2017-04-30T19:00:22 Z | sbansalcs | Port Facility (JOI17_port_facility) | C++14 | 3369 ms | 986412 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 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 n=read(); comps=n; 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; for(int i=1;i<=2*n;i++) { if(!in[i]) continue; vt.clear(); int v = ver[i]; ass(A[v]==i); for(auto c:ms) { if(c>A[v]) break; vt.push_back(c); } for(auto c:vt) { 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); } bool f=0; vt.clear(); 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.push_back(c); } for(auto c:vt) { ms.erase(ms.find(c)); } ms.insert(B[v]); } // 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 45384 KB | Output is correct |
2 | Correct | 6 ms | 45384 KB | Output is correct |
3 | Correct | 13 ms | 45384 KB | Output is correct |
4 | Correct | 13 ms | 45384 KB | Output is correct |
5 | Correct | 13 ms | 45384 KB | Output is correct |
6 | Correct | 6 ms | 45384 KB | Output is correct |
7 | Correct | 6 ms | 45384 KB | Output is correct |
8 | Correct | 16 ms | 45384 KB | Output is correct |
9 | Correct | 6 ms | 45384 KB | Output is correct |
10 | Correct | 9 ms | 45384 KB | Output is correct |
11 | Correct | 13 ms | 45384 KB | Output is correct |
12 | Correct | 9 ms | 45384 KB | Output is correct |
13 | Correct | 13 ms | 45384 KB | Output is correct |
14 | Correct | 6 ms | 45384 KB | Output is correct |
15 | Correct | 3 ms | 45384 KB | Output is correct |
16 | Correct | 13 ms | 45384 KB | Output is correct |
17 | Correct | 3 ms | 45384 KB | Output is correct |
18 | Correct | 3 ms | 45384 KB | Output is correct |
19 | Correct | 3 ms | 45384 KB | Output is correct |
20 | Correct | 16 ms | 45384 KB | Output is correct |
21 | Correct | 0 ms | 45384 KB | Output is correct |
22 | Correct | 6 ms | 45384 KB | Output is correct |
23 | Correct | 9 ms | 45384 KB | Output is correct |
24 | Correct | 9 ms | 45384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 45384 KB | Output is correct |
2 | Correct | 6 ms | 45384 KB | Output is correct |
3 | Correct | 13 ms | 45384 KB | Output is correct |
4 | Correct | 13 ms | 45384 KB | Output is correct |
5 | Correct | 13 ms | 45384 KB | Output is correct |
6 | Correct | 6 ms | 45384 KB | Output is correct |
7 | Correct | 6 ms | 45384 KB | Output is correct |
8 | Correct | 16 ms | 45384 KB | Output is correct |
9 | Correct | 6 ms | 45384 KB | Output is correct |
10 | Correct | 9 ms | 45384 KB | Output is correct |
11 | Correct | 13 ms | 45384 KB | Output is correct |
12 | Correct | 9 ms | 45384 KB | Output is correct |
13 | Correct | 13 ms | 45384 KB | Output is correct |
14 | Correct | 6 ms | 45384 KB | Output is correct |
15 | Correct | 3 ms | 45384 KB | Output is correct |
16 | Correct | 13 ms | 45384 KB | Output is correct |
17 | Correct | 3 ms | 45384 KB | Output is correct |
18 | Correct | 3 ms | 45384 KB | Output is correct |
19 | Correct | 3 ms | 45384 KB | Output is correct |
20 | Correct | 16 ms | 45384 KB | Output is correct |
21 | Correct | 0 ms | 45384 KB | Output is correct |
22 | Correct | 6 ms | 45384 KB | Output is correct |
23 | Correct | 9 ms | 45384 KB | Output is correct |
24 | Correct | 9 ms | 45384 KB | Output is correct |
25 | Correct | 13 ms | 45912 KB | Output is correct |
26 | Correct | 9 ms | 45912 KB | Output is correct |
27 | Correct | 6 ms | 45912 KB | Output is correct |
28 | Correct | 16 ms | 45912 KB | Output is correct |
29 | Correct | 9 ms | 45912 KB | Output is correct |
30 | Correct | 9 ms | 45912 KB | Output is correct |
31 | Correct | 13 ms | 45912 KB | Output is correct |
32 | Correct | 9 ms | 45912 KB | Output is correct |
33 | Correct | 9 ms | 45780 KB | Output is correct |
34 | Correct | 13 ms | 45648 KB | Output is correct |
35 | Correct | 6 ms | 45648 KB | Output is correct |
36 | Correct | 6 ms | 45648 KB | Output is correct |
37 | Correct | 13 ms | 45648 KB | Output is correct |
38 | Correct | 9 ms | 45648 KB | Output is correct |
39 | Correct | 6 ms | 45648 KB | Output is correct |
40 | Correct | 9 ms | 45648 KB | Output is correct |
41 | Correct | 206 ms | 92508 KB | Output is correct |
42 | Correct | 196 ms | 92508 KB | Output is correct |
43 | Correct | 9 ms | 45780 KB | Output is correct |
44 | Correct | 6 ms | 45780 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 45384 KB | Output is correct |
2 | Correct | 6 ms | 45384 KB | Output is correct |
3 | Correct | 13 ms | 45384 KB | Output is correct |
4 | Correct | 13 ms | 45384 KB | Output is correct |
5 | Correct | 13 ms | 45384 KB | Output is correct |
6 | Correct | 6 ms | 45384 KB | Output is correct |
7 | Correct | 6 ms | 45384 KB | Output is correct |
8 | Correct | 16 ms | 45384 KB | Output is correct |
9 | Correct | 6 ms | 45384 KB | Output is correct |
10 | Correct | 9 ms | 45384 KB | Output is correct |
11 | Correct | 13 ms | 45384 KB | Output is correct |
12 | Correct | 9 ms | 45384 KB | Output is correct |
13 | Correct | 13 ms | 45384 KB | Output is correct |
14 | Correct | 6 ms | 45384 KB | Output is correct |
15 | Correct | 3 ms | 45384 KB | Output is correct |
16 | Correct | 13 ms | 45384 KB | Output is correct |
17 | Correct | 3 ms | 45384 KB | Output is correct |
18 | Correct | 3 ms | 45384 KB | Output is correct |
19 | Correct | 3 ms | 45384 KB | Output is correct |
20 | Correct | 16 ms | 45384 KB | Output is correct |
21 | Correct | 0 ms | 45384 KB | Output is correct |
22 | Correct | 6 ms | 45384 KB | Output is correct |
23 | Correct | 9 ms | 45384 KB | Output is correct |
24 | Correct | 9 ms | 45384 KB | Output is correct |
25 | Correct | 13 ms | 45912 KB | Output is correct |
26 | Correct | 9 ms | 45912 KB | Output is correct |
27 | Correct | 6 ms | 45912 KB | Output is correct |
28 | Correct | 16 ms | 45912 KB | Output is correct |
29 | Correct | 9 ms | 45912 KB | Output is correct |
30 | Correct | 9 ms | 45912 KB | Output is correct |
31 | Correct | 13 ms | 45912 KB | Output is correct |
32 | Correct | 9 ms | 45912 KB | Output is correct |
33 | Correct | 9 ms | 45780 KB | Output is correct |
34 | Correct | 13 ms | 45648 KB | Output is correct |
35 | Correct | 6 ms | 45648 KB | Output is correct |
36 | Correct | 6 ms | 45648 KB | Output is correct |
37 | Correct | 13 ms | 45648 KB | Output is correct |
38 | Correct | 9 ms | 45648 KB | Output is correct |
39 | Correct | 6 ms | 45648 KB | Output is correct |
40 | Correct | 9 ms | 45648 KB | Output is correct |
41 | Correct | 206 ms | 92508 KB | Output is correct |
42 | Correct | 196 ms | 92508 KB | Output is correct |
43 | Correct | 9 ms | 45780 KB | Output is correct |
44 | Correct | 6 ms | 45780 KB | Output is correct |
45 | Correct | 256 ms | 71784 KB | Output is correct |
46 | Correct | 316 ms | 73632 KB | Output is correct |
47 | Correct | 259 ms | 75084 KB | Output is correct |
48 | Correct | 263 ms | 69408 KB | Output is correct |
49 | Correct | 273 ms | 75612 KB | Output is correct |
50 | Correct | 103 ms | 59112 KB | Output is correct |
51 | Correct | 159 ms | 63204 KB | Output is correct |
52 | Correct | 123 ms | 54756 KB | Output is correct |
53 | Correct | 103 ms | 59508 KB | Output is correct |
54 | Correct | 66 ms | 54756 KB | Output is correct |
55 | Correct | 63 ms | 54756 KB | Output is correct |
56 | Correct | 79 ms | 54756 KB | Output is correct |
57 | Correct | 156 ms | 59508 KB | Output is correct |
58 | Correct | 93 ms | 54756 KB | Output is correct |
59 | Correct | 136 ms | 56736 KB | Output is correct |
60 | Correct | 159 ms | 60564 KB | Output is correct |
61 | Correct | 199 ms | 65976 KB | Output is correct |
62 | Correct | 93 ms | 54756 KB | Output is correct |
63 | Correct | 73 ms | 54756 KB | Output is correct |
64 | Correct | 66 ms | 54888 KB | Output is correct |
65 | Correct | 76 ms | 54756 KB | Output is correct |
66 | Correct | 76 ms | 54756 KB | Output is correct |
67 | Runtime error | 3369 ms | 986412 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
68 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 45384 KB | Output is correct |
2 | Correct | 6 ms | 45384 KB | Output is correct |
3 | Correct | 13 ms | 45384 KB | Output is correct |
4 | Correct | 13 ms | 45384 KB | Output is correct |
5 | Correct | 13 ms | 45384 KB | Output is correct |
6 | Correct | 6 ms | 45384 KB | Output is correct |
7 | Correct | 6 ms | 45384 KB | Output is correct |
8 | Correct | 16 ms | 45384 KB | Output is correct |
9 | Correct | 6 ms | 45384 KB | Output is correct |
10 | Correct | 9 ms | 45384 KB | Output is correct |
11 | Correct | 13 ms | 45384 KB | Output is correct |
12 | Correct | 9 ms | 45384 KB | Output is correct |
13 | Correct | 13 ms | 45384 KB | Output is correct |
14 | Correct | 6 ms | 45384 KB | Output is correct |
15 | Correct | 3 ms | 45384 KB | Output is correct |
16 | Correct | 13 ms | 45384 KB | Output is correct |
17 | Correct | 3 ms | 45384 KB | Output is correct |
18 | Correct | 3 ms | 45384 KB | Output is correct |
19 | Correct | 3 ms | 45384 KB | Output is correct |
20 | Correct | 16 ms | 45384 KB | Output is correct |
21 | Correct | 0 ms | 45384 KB | Output is correct |
22 | Correct | 6 ms | 45384 KB | Output is correct |
23 | Correct | 9 ms | 45384 KB | Output is correct |
24 | Correct | 9 ms | 45384 KB | Output is correct |
25 | Correct | 13 ms | 45912 KB | Output is correct |
26 | Correct | 9 ms | 45912 KB | Output is correct |
27 | Correct | 6 ms | 45912 KB | Output is correct |
28 | Correct | 16 ms | 45912 KB | Output is correct |
29 | Correct | 9 ms | 45912 KB | Output is correct |
30 | Correct | 9 ms | 45912 KB | Output is correct |
31 | Correct | 13 ms | 45912 KB | Output is correct |
32 | Correct | 9 ms | 45912 KB | Output is correct |
33 | Correct | 9 ms | 45780 KB | Output is correct |
34 | Correct | 13 ms | 45648 KB | Output is correct |
35 | Correct | 6 ms | 45648 KB | Output is correct |
36 | Correct | 6 ms | 45648 KB | Output is correct |
37 | Correct | 13 ms | 45648 KB | Output is correct |
38 | Correct | 9 ms | 45648 KB | Output is correct |
39 | Correct | 6 ms | 45648 KB | Output is correct |
40 | Correct | 9 ms | 45648 KB | Output is correct |
41 | Correct | 206 ms | 92508 KB | Output is correct |
42 | Correct | 196 ms | 92508 KB | Output is correct |
43 | Correct | 9 ms | 45780 KB | Output is correct |
44 | Correct | 6 ms | 45780 KB | Output is correct |
45 | Correct | 256 ms | 71784 KB | Output is correct |
46 | Correct | 316 ms | 73632 KB | Output is correct |
47 | Correct | 259 ms | 75084 KB | Output is correct |
48 | Correct | 263 ms | 69408 KB | Output is correct |
49 | Correct | 273 ms | 75612 KB | Output is correct |
50 | Correct | 103 ms | 59112 KB | Output is correct |
51 | Correct | 159 ms | 63204 KB | Output is correct |
52 | Correct | 123 ms | 54756 KB | Output is correct |
53 | Correct | 103 ms | 59508 KB | Output is correct |
54 | Correct | 66 ms | 54756 KB | Output is correct |
55 | Correct | 63 ms | 54756 KB | Output is correct |
56 | Correct | 79 ms | 54756 KB | Output is correct |
57 | Correct | 156 ms | 59508 KB | Output is correct |
58 | Correct | 93 ms | 54756 KB | Output is correct |
59 | Correct | 136 ms | 56736 KB | Output is correct |
60 | Correct | 159 ms | 60564 KB | Output is correct |
61 | Correct | 199 ms | 65976 KB | Output is correct |
62 | Correct | 93 ms | 54756 KB | Output is correct |
63 | Correct | 73 ms | 54756 KB | Output is correct |
64 | Correct | 66 ms | 54888 KB | Output is correct |
65 | Correct | 76 ms | 54756 KB | Output is correct |
66 | Correct | 76 ms | 54756 KB | Output is correct |
67 | Runtime error | 3369 ms | 986412 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
68 | Halted | 0 ms | 0 KB | - |