oj.uz

Submission #52987

# Submission time Handle Problem Language Result Execution time Memory
52987 2018-06-27T13:15:30 Z polyfish Usmjeri (COCI17_usmjeri) C++14
98 / 140
 2000 ms 73196 KB 
//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cerr << #x << " = " << x << '\n';}
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "data"

const int MAX_N = 300002;
const int MOD = 1000000007;

int n, m, l[MAX_N], dir[MAX_N], p[22][MAX_N];
pair<int, int> e[MAX_N];
vector<int> tr[MAX_N], g[MAX_N];

int readInt() {
	char c;
	for (c = getchar(); c<'0' || c>'9'; c = getchar());
	int res = c - '0';
	for (c = getchar(); '0'<=c && c<='9'; c = getchar())
		res = res * 10 + c - '0';
	return res;
}

struct DSU {
	int lab[MAX_N];

	void init() {
		memset(lab, 0, sizeof(lab));
	}

	int findset(int u) {
		return lab[u]==0 ? u : lab[u]=findset(lab[u]);
	}

	void uni(int s, int t) {
		s = findset(s); t = findset(t);
		if (s==t)
			return;
		if (l[s]>l[t])
			swap(s, t);
		lab[t] = s;
	}
} D1, D2, D3;

void enter() {
	n = readInt();
	m = readInt();
	for (int i=1; i<n; ++i) {
		int u = readInt(), v = readInt();
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
	for (int i=1; i<=m; ++i) {
		e[i] = make_pair(readInt(), readInt());
	}
}

void fixRoot(int u) {
	for (int i=0; i<tr[u].size(); ++i) {
		int v = tr[u][i];
		if (v!=p[0][u]) {
			p[0][v] = u;
			l[v] = l[u] + 1;
			fixRoot(v);
		}
	}
}

int lca(int x, int y) {
	for (int k=19; k>=0; --k)
		if (l[p[k][x]]>=l[y])
			x = p[k][x];
	for (int k=19; k>=0; --k)
		if (l[p[k][y]]>=l[x])
			y = p[k][y];
	for (int k=19; k>=0; --k) {
		if (p[k][x]!=p[k][y]) {
			x = p[k][x]; y = p[k][y];
		}
	}
	while (x!=y) {
		x = p[0][x]; y = p[0][y];
	}
	return x;
}

int prevNode(int anc, int u) {
	if (u==anc)
		return 0;
	for (int k=19; k>=0; --k)
		if (l[p[k][u]]>l[anc])
			u = p[k][u];
	return u;
}

void make_graph() {
	D1.init();
	D2.init();
	for (int i=1; i<=m; ++i) {
		int u = e[i].first, v = e[i].second, r = lca(u, v);
		int prevU = prevNode(r, u), prevV = prevNode(r, v);
		while (l[p[0][v]]>l[r]) {
			int par = p[0][v];
			g[par].push_back(v);
			g[v].push_back(par);
			D1.uni(v, par);
			v = D1.findset(v);
		}
		while (l[p[0][u]]>l[r]) {
			int par = p[0][u];
			g[par].push_back(u);
			g[u].push_back(par);
			D2.uni(u, par);
			u = D2.findset(u);
		}
		if (prevU && prevV) {
			g[prevU].push_back(prevV);
			g[prevV].push_back(prevU);
		}
	}
}

void visit(int u) {
	int _next;
	for (int i=0; i<g[u].size(); ++i) {
		int v = g[u][i];
		if (dir[v]==0) {
			if (v==p[0][u] || u==p[0][v])
				dir[v] = dir[u];
			else
				dir[v] = -dir[u];
			visit(v);
		}
	}
}

bool check() {
	D1.init();
	D2.init();
	//debug(dir[3]);
	//debug(dir[4]);
	for (int i=1; i<=m; ++i) {
		int u = e[i].first, v = e[i].second, r = lca(u, v);
		int prevU = prevNode(r, u), prevV = prevNode(r, v);
		if (dir[prevU]==dir[prevV])
			return false;
		while (l[p[0][v]]>l[r]) {
			int par = p[0][v];
			if (dir[v]!=dir[par])
				return false;
			D1.uni(v, par);
			v = D1.findset(v);
		}
		while (l[p[0][u]]>l[r]) {
			int par = p[0][u];
			if (dir[u]!=dir[par])
				return false;
			D2.uni(u, par);
			u = D2.findset(u);
		}
	}
	return true;
}

int main() {
	//freopen(FILE_NAME".inp", "r", stdin);
	//freopen(FILE_NAME".out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	l[1] = 1;
	fixRoot(1);
	for (int i=1; i<=19; ++i)
		for (int j=1; j<=n; ++j)
			p[i][j] = p[i-1][p[i-1][j]];
	make_graph();
	int res = 1;
	for (int i=2; i<=n; ++i) {
		if (dir[i]==0) {
			dir[i] = 1;
			visit(i);
			res = (res * 2) % MOD;
		}
	}
	//debug(res);
	if (check()) {
		cout << res;
	}
	else {
		cout << 0;
	}
}

Compilation message

usmjeri.cpp: In function 'void fixRoot(int)':
usmjeri.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<tr[u].size(); ++i) {
                ~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void visit(int)':
usmjeri.cpp:129:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<g[u].size(); ++i) {
                ~^~~~~~~~~~~~
usmjeri.cpp:128:6: warning: unused variable '_next' [-Wunused-variable]
  int _next;
      ^~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 38648 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 73196 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 73196 KB Output is correct
2 Correct 18 ms 73196 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 73196 KB Output is correct
2 Correct 17 ms 73196 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 73196 KB Output is correct
2 Correct 21 ms 73196 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 73196 KB Output is correct
2 Correct 25 ms 73196 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 73196 KB Output is correct
2 Correct 1425 ms 73196 KB Output is correct
3 Correct 568 ms 73196 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 73196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 73196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 73196 KB Time limit exceeded
2 Halted 0 ms 0 KB -