Submission #245623

#	Time	Username	Problem	Language	Result	Execution time	Memory
245623		cki86201	Port Facility (JOI17_port_facility)	C++11	100 / 100	1126 ms	159924 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

int N, X[2000020], A[1000010], B[1000010];
vector <int> E[1000010];
int nxt[1000010], pre[1000010], tail[1000010];
int pp[1000010], vis[1000010]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
vector <pii> edge;

void dfs(int x, int c) {
	vis[x] = c;
	for(int e : E[x]) if(!vis[e]) dfs(e, 3 - c);
}

int main() {
	scanf("%d", &N);
	for(int i=1;i<=N;i++) scanf("%d%d", A+i, B+i);
	for(int i=1;i<=N;i++) X[A[i]] = -i, X[B[i]] = i, nxt[i] = pre[i] = tail[i] = i;
	vector <pii> w;
	for(int i=1;i<=N;i++) pp[i] = i;
	for(int i=1;i<=2*N;i++) {
		int v = X[i];
		if(v < 0) w.pb({-v, 1});
		else {
			int a = Find(v), px = -1, cnt = 0;
			while(szz(w) && w.back().Fi != a) {
				int pa = w.back().Fi;
				cnt += w.back().Se;
				if(px != -1) {
					pp[px] = pa;
					int t1 = tail[pa], t2 = px;
					if(B[t1] < B[t2]) {
						puts("0"); return 0;
					}
					nxt[t1] = t2; pre[t2] = t1;
					tail[pa] = tail[px];
				}
				px = pa;
				w.pop_back();
			}
			if(w.back().Se > 1) {
				int p = w.back().Fi;
				tail[p] = pre[tail[p]];
				--w.back().Se;
			}
			else w.pop_back();
			if(px != -1) edge.pb({px, a}), w.pb({px, cnt});
		}
	}
	for(auto &[x, y] : edge) x = Find(x), y = Find(y), E[x].pb(y), E[y].pb(x);
	int ans = 1;
	for(int i=1;i<=N;i++) if(pp[i] == i && !vis[i]) {
		dfs(i, 1);
		ans = ans * 2 % 1000000007;
	}
	for(int i=1;i<=N;i++) for(int e : E[i]) if(vis[i] == vis[e]) ans = 0;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:61:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for(auto &[x, y] : edge) x = Find(x), y = Find(y), E[x].pb(y), E[y].pb(x);
            ^
port_facility.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
port_facility.cpp:28:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d%d", A+i, B+i);
                        ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22