Submission #447813

#	Time	Username	Problem	Language	Result	Execution time	Memory
447813		Haruto810198	Port Facility (JOI17_port_facility)	C++17	22 / 100	12 ms	8396 KiB

port_facility

#include <bits/stdc++.h>

typedef long long ll;
const int N = 2000054, mod = 1000000007;

int n;
int p[N], id[N];
int cnt = 0, a[N];
int left[N], next[N];

ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;}

// list
int ancestor(int x) {return p[x] == x ? x : (p[x] = ancestor(p[x]));}

namespace Graph {
	int E = 0;
	int to[N], first[N], next[N];
	int col[N];

	inline void addedge(int u, int v) {
		to[++E] = v, next[E] = first[u], first[u] = E;
		to[++E] = u, next[E] = first[v], first[v] = E;
	}

	bool dfs(int x) {
		int i, y;
		for (i = first[x]; i; i = next[i])
			if (~col[y = to[i]] ? col[y] == col[x] : (col[y] = !col[x], !dfs(y))) return false;
		return true;
	}

	int main() {
		int i, c = 0;
		memset(col, -1, sizeof col);
		for (i = 1; i <= n; ++i) if (!~col[i] && (++c, !dfs(i))) return 0;
		return c;
	}
}

int main() {
	int _, __, i, j, l, r;
	scanf("%d", &n);
  	
  	assert(n <= 2000);
  	
	for (i = 1; i <= n; ++i) scanf("%d%d", &l, &r), id[l] = id[r] = i;
	std::iota(p, p + (n + 2), 0), std::iota(next, next + (n + 1), 0);
	for (_ = 1; _ <= n * 2; ++_)
		if (!left[i = id[_]]) a[++cnt] = i, left[i] = cnt;
		else
			for (j = p[left[i]] = ancestor(left[i] + 1); j <= cnt; j = __)
				Graph::addedge(a[j], i), __ = ancestor(next[j] + 1), next[j] = cnt;
	printf("%d\n", (r = Graph::main()) ? (int)PowerMod(2, r) : 0);
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:47:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  for (i = 1; i <= n; ++i) scanf("%d%d", &l, &r), id[l] = id[r] = i;
      |                           ~~~~~^~~~~~~~~~~~~~~~

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