oj.uz

Submission #35389

# Submission time Handle Problem Language Result Execution time Memory
35389 2017-11-21T16:09:54 Z RockyB Usmjeri (COCI17_usmjeri) C++14
56 / 140
 2000 ms 262144 KB 
/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)3e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
int lvl[N], up[N];
vector <int> g[N], g1[N], g2[N];

unordered_map <int, int> st[N];

int get(int v, int u) {
	static int id = 0;
	if (v > u) swap(v, u);
	if (!st[v].count(u)) st[v][u] = ++id;
	return st[v][u];
}
void dfs(int v = 1, int p = 0) {
	lvl[v] = lvl[p] + 1;
	up[v] = p;
	for (auto to : g[v]) {
		if (to != p) {
			get(v, to);
			dfs(to, v);
		}
	}
}
int lca(int x, int y) {
	while (lvl[x] > lvl[y]) x = up[x];
	while (lvl[x] < lvl[y]) y = up[y];
	while (x != y) x = up[x], y = up[y];
	return x;
}

bool was[N];
int clr[N];
void dfs1(int v) {
	was[v] = 1;
	for (auto to : g1[v]) {
		if (!was[to]) {
			clr[to] = clr[v];
			dfs1(to);
		}
		else if (clr[to] != clr[v]) {
			cout << 0, ioi
		}
	}	
	for (auto to : g2[v]) {
		if (!was[to]) {
			clr[to] = 3 - clr[v];
			dfs1(to);
		}
		else if (clr[to] == clr[v]) {
			cout << 0, ioi
		}
	}
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
		freopen ("E.out", "w", stdout);
	#endif	
	scanf ("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int v, u;
		scanf ("%d%d", &v, &u);
		g[v].pb(u);
		g[u].pb(v);
	}
	dfs();
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf ("%d%d", &x, &y);
		int batya = lca(x, y);
		if (batya == x || batya == y) {
			if (batya == x) swap(x, y);
			int last = -1;
			while (x != batya) {
				int cur = get(x, up[x]);
				if (last != -1) {
					g1[cur].pb(last);
					g1[last].pb(cur);
				}
				last = cur;
				x = up[x];
			}
		}
		else {
			int last1 = -1, last2 = -1;
			while (x != batya) {
				int cur = get(x, up[x]);
				if (last1 != -1) {
					g1[cur].pb(last1);
					g1[last1].pb(cur);
				}
				last1 = cur;
				x = up[x];
			}
			while (y != batya) {
				int cur = get(y, up[y]);
				if (last2 != -1) {
					g1[cur].pb(last2);
					g1[last2].pb(cur);
				}
				last2 = cur;
				y = up[y];
			}
			g2[last1].pb(last2);
			g2[last2].pb(last1);
		}
	}
	int ans = 1;
	for (int i = 1; i < n; i++) {
		if (!was[i]) {
			clr[i] = 1;
			dfs1(i);
			ans = ans * 1ll * 2 % mod;
		}
	}
	cout << ans;
	ioi
}

Compilation message

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:91:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
                        ^
usmjeri.cpp:94:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &v, &u);
                         ^
usmjeri.cpp:101:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &x, &y);
                         ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 262144 KB Execution timed out

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 262144 KB Execution timed out

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 43464 KB Output is correct
2 Correct 9 ms 43596 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43464 KB Output is correct
2 Correct 13 ms 43596 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43860 KB Output is correct
2 Correct 23 ms 43860 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 215364 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 262144 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 262144 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 262144 KB Execution timed out
2 Halted 0 ms 0 KB -