oj.uz

Submission #137847

# Submission time Handle Problem Language Result Execution time Memory
137847 2019-07-28T11:04:56 Z Retro3014 Port Facility (JOI17_port_facility) C++17
100 / 100
 2701 ms 505612 KB 
#include <bits/stdc++.h>
 
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
 
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll DIV = 1000000007;
const int MAX_N = 1000000;
int N;
vector<pii> vt;
 
bool zero = false;
vector<int> gp[MAX_N*2+1];
int c[MAX_N*2+1];
 
 
int t, k;
 
struct SEG{
	
	struct NODE{
		int l=-1, r=-1;
		vector<int> v;
		int sz=0;
	};
	vector<NODE> seg;
	int SZ, cnt;
	void Init(int x){
		SZ = x; seg.resize(SZ*2);
		cnt = 1;
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		//seg[idx].v.reserve(e-s+1);
		if(s==e)	return;
		seg[idx].l = cnt++; seg[idx].r = cnt++;
		init(seg[idx].l, s, ((s+e)>>1));
		init(seg[idx].r, ((s+e)>>1)+1, e);
	}
	void Update(int x){
		update(0, 1, SZ, x);
	}
	void update(int idx, int s, int e, int k){
		//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
		if(seg[idx].v.empty() || seg[idx].v.back()!=-1)	seg[idx].v.pb(k);
		if(s==e)	return;
		if(k<=((s+e)>>1)){
			update(seg[idx].l, s, ((s+e)>>1), k);
		}else{
			update(seg[idx].r, ((s+e)>>1)+1, e, k);
		}
	}
	void Calc(int x, int y){
		calc(0, 1, SZ, x, y);
	}
	void calc(int idx, int s, int e, int x, int y){
		if(seg[idx].v.empty())	return;
		//cout<<idx<<" "<<s<<" "<<e<<" "<<x<<" "<<y<<endl;
		if(x<=s && e<=y){
			if(seg[idx].v.back()==-1){
				zero = true;
				return;
			}
			if(e==y){
				while(!seg[idx].v.empty()){
					gp[y].pb(seg[idx].v.back()); gp[seg[idx].v.back()].pb(y);
					seg[idx].v.pop_back();
				}
				seg[idx].v.pb(-1);
				return;
			}
			for (auto &t : seg[idx].v)gp[t].pb(y), gp[y].pb(t);
	         while (seg[idx].v.size() > 1)seg[idx].v.pop_back();
	         return;
		}else if(x>e || y<s)	return;
		calc(seg[idx].l, s, ((s+e)>>1), x, y);
		calc(seg[idx].r, ((s+e)>>1)+1, e, x, y);
	}
};
 
SEG Seg;
 
vector<int> dq;
 
void bfs(int x){
	dq.pb(x);
	while(!dq.empty()){
		x = dq.back(); dq.pop_back();
		for(int i : gp[x]){
			if(c[i]==0){
				c[i] = 3 - c[x];
				dq.pb(i);
			}else if(c[i]==c[x]){
				zero=true;
				return;
			}
		}
	}
}
 
vector<int> sc;
 
int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		vt.pb({a, b});
	}
	sort(vt.begin(), vt.end());
	int idx = 0;
	//UF.init(N*2);
	Seg.Init(N*2);
	for(int i=1; i<=N*2; i++){
		if(idx<N && vt[idx].first==i){
			//cout<<vt[idx].first<<" "<<vt[idx].second<<endl;
			Seg.Calc(vt[idx].first, vt[idx].second);
			if(zero){
				printf("0");
				return 0;
			}
			Seg.Update(vt[idx].second);
			idx++;
		}else{
			sc.pb(i);
		}
	}
	ll ans = 1;
	//ll num=0;
	for(int i : sc){
		//num+=gp[i].size();
		if(c[i]==0){
			c[i] = 1;
			bfs(i);
			if(zero){
				printf("0");
				return 0;
			}
			ans = (ans*(ll)2)%DIV;
		}
	}
	//cout<<num<<endl;
	cout<<ans;
	return 0;
}

Compilation message

port_facility.cpp: In function 'int main()':
port_facility.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 50 ms 47344 KB Output is correct
4 Correct 46 ms 47332 KB Output is correct
5 Correct 45 ms 47224 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 54 ms 47224 KB Output is correct
9 Correct 48 ms 47224 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47372 KB Output is correct
12 Correct 45 ms 47480 KB Output is correct
13 Correct 45 ms 47324 KB Output is correct
14 Correct 46 ms 47480 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 45 ms 47352 KB Output is correct
17 Correct 45 ms 47352 KB Output is correct
18 Correct 45 ms 47352 KB Output is correct
19 Correct 45 ms 47372 KB Output is correct
20 Correct 46 ms 47352 KB Output is correct
21 Correct 46 ms 47352 KB Output is correct
22 Correct 45 ms 47352 KB Output is correct
23 Correct 46 ms 47224 KB Output is correct
24 Correct 45 ms 47352 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 50 ms 47344 KB Output is correct
4 Correct 46 ms 47332 KB Output is correct
5 Correct 45 ms 47224 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 54 ms 47224 KB Output is correct
9 Correct 48 ms 47224 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47372 KB Output is correct
12 Correct 45 ms 47480 KB Output is correct
13 Correct 45 ms 47324 KB Output is correct
14 Correct 46 ms 47480 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 45 ms 47352 KB Output is correct
17 Correct 45 ms 47352 KB Output is correct
18 Correct 45 ms 47352 KB Output is correct
19 Correct 45 ms 47372 KB Output is correct
20 Correct 46 ms 47352 KB Output is correct
21 Correct 46 ms 47352 KB Output is correct
22 Correct 45 ms 47352 KB Output is correct
23 Correct 46 ms 47224 KB Output is correct
24 Correct 45 ms 47352 KB Output is correct
25 Correct 50 ms 47992 KB Output is correct
26 Correct 49 ms 47992 KB Output is correct
27 Correct 50 ms 47992 KB Output is correct
28 Correct 50 ms 47992 KB Output is correct
29 Correct 49 ms 47992 KB Output is correct
30 Correct 50 ms 47992 KB Output is correct
31 Correct 59 ms 47992 KB Output is correct
32 Correct 76 ms 47992 KB Output is correct
33 Correct 53 ms 47992 KB Output is correct
34 Correct 57 ms 47864 KB Output is correct
35 Correct 58 ms 47992 KB Output is correct
36 Correct 57 ms 47868 KB Output is correct
37 Correct 49 ms 47608 KB Output is correct
38 Correct 47 ms 47736 KB Output is correct
39 Correct 49 ms 48124 KB Output is correct
40 Correct 49 ms 47992 KB Output is correct
41 Correct 48 ms 47992 KB Output is correct
42 Correct 47 ms 47992 KB Output is correct
43 Correct 49 ms 47992 KB Output is correct
44 Correct 49 ms 47992 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 50 ms 47344 KB Output is correct
4 Correct 46 ms 47332 KB Output is correct
5 Correct 45 ms 47224 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 54 ms 47224 KB Output is correct
9 Correct 48 ms 47224 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47372 KB Output is correct
12 Correct 45 ms 47480 KB Output is correct
13 Correct 45 ms 47324 KB Output is correct
14 Correct 46 ms 47480 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 45 ms 47352 KB Output is correct
17 Correct 45 ms 47352 KB Output is correct
18 Correct 45 ms 47352 KB Output is correct
19 Correct 45 ms 47372 KB Output is correct
20 Correct 46 ms 47352 KB Output is correct
21 Correct 46 ms 47352 KB Output is correct
22 Correct 45 ms 47352 KB Output is correct
23 Correct 46 ms 47224 KB Output is correct
24 Correct 45 ms 47352 KB Output is correct
25 Correct 50 ms 47992 KB Output is correct
26 Correct 49 ms 47992 KB Output is correct
27 Correct 50 ms 47992 KB Output is correct
28 Correct 50 ms 47992 KB Output is correct
29 Correct 49 ms 47992 KB Output is correct
30 Correct 50 ms 47992 KB Output is correct
31 Correct 59 ms 47992 KB Output is correct
32 Correct 76 ms 47992 KB Output is correct
33 Correct 53 ms 47992 KB Output is correct
34 Correct 57 ms 47864 KB Output is correct
35 Correct 58 ms 47992 KB Output is correct
36 Correct 57 ms 47868 KB Output is correct
37 Correct 49 ms 47608 KB Output is correct
38 Correct 47 ms 47736 KB Output is correct
39 Correct 49 ms 48124 KB Output is correct
40 Correct 49 ms 47992 KB Output is correct
41 Correct 48 ms 47992 KB Output is correct
42 Correct 47 ms 47992 KB Output is correct
43 Correct 49 ms 47992 KB Output is correct
44 Correct 49 ms 47992 KB Output is correct
45 Correct 262 ms 84572 KB Output is correct
46 Correct 267 ms 84588 KB Output is correct
47 Correct 256 ms 84076 KB Output is correct
48 Correct 281 ms 84952 KB Output is correct
49 Correct 299 ms 84328 KB Output is correct
50 Correct 180 ms 69736 KB Output is correct
51 Correct 174 ms 73360 KB Output is correct
52 Correct 202 ms 82440 KB Output is correct
53 Correct 192 ms 79840 KB Output is correct
54 Correct 105 ms 65180 KB Output is correct
55 Correct 106 ms 65132 KB Output is correct
56 Correct 99 ms 65128 KB Output is correct
57 Correct 219 ms 84972 KB Output is correct
58 Correct 203 ms 81868 KB Output is correct
59 Correct 234 ms 83876 KB Output is correct
60 Correct 265 ms 83948 KB Output is correct
61 Correct 258 ms 83988 KB Output is correct
62 Correct 235 ms 84112 KB Output is correct
63 Correct 146 ms 70896 KB Output is correct
64 Correct 234 ms 82024 KB Output is correct
65 Correct 101 ms 65260 KB Output is correct
66 Correct 101 ms 65132 KB Output is correct
67 Correct 275 ms 90404 KB Output is correct
68 Correct 285 ms 90280 KB Output is correct
69 Correct 287 ms 91284 KB Output is correct
70 Correct 283 ms 91300 KB Output is correct
71 Correct 205 ms 83308 KB Output is correct
72 Correct 206 ms 83308 KB Output is correct
73 Correct 209 ms 84028 KB Output is correct
74 Correct 214 ms 83884 KB Output is correct
75 Correct 227 ms 85536 KB Output is correct
76 Correct 237 ms 85492 KB Output is correct
77 Correct 229 ms 85520 KB Output is correct
78 Correct 263 ms 84688 KB Output is correct
79 Correct 264 ms 84488 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47352 KB Output is correct
2 Correct 45 ms 47352 KB Output is correct
3 Correct 50 ms 47344 KB Output is correct
4 Correct 46 ms 47332 KB Output is correct
5 Correct 45 ms 47224 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 55 ms 47352 KB Output is correct
8 Correct 54 ms 47224 KB Output is correct
9 Correct 48 ms 47224 KB Output is correct
10 Correct 45 ms 47352 KB Output is correct
11 Correct 45 ms 47372 KB Output is correct
12 Correct 45 ms 47480 KB Output is correct
13 Correct 45 ms 47324 KB Output is correct
14 Correct 46 ms 47480 KB Output is correct
15 Correct 45 ms 47224 KB Output is correct
16 Correct 45 ms 47352 KB Output is correct
17 Correct 45 ms 47352 KB Output is correct
18 Correct 45 ms 47352 KB Output is correct
19 Correct 45 ms 47372 KB Output is correct
20 Correct 46 ms 47352 KB Output is correct
21 Correct 46 ms 47352 KB Output is correct
22 Correct 45 ms 47352 KB Output is correct
23 Correct 46 ms 47224 KB Output is correct
24 Correct 45 ms 47352 KB Output is correct
25 Correct 50 ms 47992 KB Output is correct
26 Correct 49 ms 47992 KB Output is correct
27 Correct 50 ms 47992 KB Output is correct
28 Correct 50 ms 47992 KB Output is correct
29 Correct 49 ms 47992 KB Output is correct
30 Correct 50 ms 47992 KB Output is correct
31 Correct 59 ms 47992 KB Output is correct
32 Correct 76 ms 47992 KB Output is correct
33 Correct 53 ms 47992 KB Output is correct
34 Correct 57 ms 47864 KB Output is correct
35 Correct 58 ms 47992 KB Output is correct
36 Correct 57 ms 47868 KB Output is correct
37 Correct 49 ms 47608 KB Output is correct
38 Correct 47 ms 47736 KB Output is correct
39 Correct 49 ms 48124 KB Output is correct
40 Correct 49 ms 47992 KB Output is correct
41 Correct 48 ms 47992 KB Output is correct
42 Correct 47 ms 47992 KB Output is correct
43 Correct 49 ms 47992 KB Output is correct
44 Correct 49 ms 47992 KB Output is correct
45 Correct 262 ms 84572 KB Output is correct
46 Correct 267 ms 84588 KB Output is correct
47 Correct 256 ms 84076 KB Output is correct
48 Correct 281 ms 84952 KB Output is correct
49 Correct 299 ms 84328 KB Output is correct
50 Correct 180 ms 69736 KB Output is correct
51 Correct 174 ms 73360 KB Output is correct
52 Correct 202 ms 82440 KB Output is correct
53 Correct 192 ms 79840 KB Output is correct
54 Correct 105 ms 65180 KB Output is correct
55 Correct 106 ms 65132 KB Output is correct
56 Correct 99 ms 65128 KB Output is correct
57 Correct 219 ms 84972 KB Output is correct
58 Correct 203 ms 81868 KB Output is correct
59 Correct 234 ms 83876 KB Output is correct
60 Correct 265 ms 83948 KB Output is correct
61 Correct 258 ms 83988 KB Output is correct
62 Correct 235 ms 84112 KB Output is correct
63 Correct 146 ms 70896 KB Output is correct
64 Correct 234 ms 82024 KB Output is correct
65 Correct 101 ms 65260 KB Output is correct
66 Correct 101 ms 65132 KB Output is correct
67 Correct 275 ms 90404 KB Output is correct
68 Correct 285 ms 90280 KB Output is correct
69 Correct 287 ms 91284 KB Output is correct
70 Correct 283 ms 91300 KB Output is correct
71 Correct 205 ms 83308 KB Output is correct
72 Correct 206 ms 83308 KB Output is correct
73 Correct 209 ms 84028 KB Output is correct
74 Correct 214 ms 83884 KB Output is correct
75 Correct 227 ms 85536 KB Output is correct
76 Correct 237 ms 85492 KB Output is correct
77 Correct 229 ms 85520 KB Output is correct
78 Correct 263 ms 84688 KB Output is correct
79 Correct 264 ms 84488 KB Output is correct
80 Correct 2507 ms 433700 KB Output is correct
81 Correct 2505 ms 432464 KB Output is correct
82 Correct 2565 ms 423836 KB Output is correct
83 Correct 2512 ms 430180 KB Output is correct
84 Correct 2569 ms 429580 KB Output is correct
85 Correct 1420 ms 312844 KB Output is correct
86 Correct 2223 ms 380820 KB Output is correct
87 Correct 1703 ms 401436 KB Output is correct
88 Correct 1633 ms 374264 KB Output is correct
89 Correct 631 ms 226568 KB Output is correct
90 Correct 632 ms 226512 KB Output is correct
91 Correct 627 ms 226384 KB Output is correct
92 Correct 1964 ms 425260 KB Output is correct
93 Correct 1738 ms 393744 KB Output is correct
94 Correct 2144 ms 423592 KB Output is correct
95 Correct 2325 ms 425388 KB Output is correct
96 Correct 2374 ms 427900 KB Output is correct
97 Correct 2168 ms 425440 KB Output is correct
98 Correct 1648 ms 348496 KB Output is correct
99 Correct 1784 ms 354400 KB Output is correct
100 Correct 656 ms 227392 KB Output is correct
101 Correct 642 ms 227212 KB Output is correct
102 Correct 2641 ms 498608 KB Output is correct
103 Correct 2626 ms 498792 KB Output is correct
104 Correct 2697 ms 505612 KB Output is correct
105 Correct 2701 ms 504132 KB Output is correct
106 Correct 1779 ms 409456 KB Output is correct
107 Correct 1828 ms 409348 KB Output is correct
108 Correct 1818 ms 414404 KB Output is correct
109 Correct 1816 ms 414288 KB Output is correct
110 Correct 1981 ms 432752 KB Output is correct
111 Correct 1999 ms 432756 KB Output is correct
112 Correct 1990 ms 432660 KB Output is correct
113 Correct 2501 ms 424652 KB Output is correct
114 Correct 2480 ms 433524 KB Output is correct