oj.uz

답안 #35458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35458 2017-11-22T04:54:59 Z RockyB Usmjeri (COCI17_usmjeri) C++14
126 / 140
 936 ms 109232 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][20], id[N];

int p[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];
}

int tmr;
int tin[N], tout[N];
void dfs(int v = 1, int p = 0) {
	lvl[v] = lvl[p] + 1;
	up[v][0] = p;
	tin[v] = ++tmr;
	for (int i = 1; i <= 19; i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
	}
	for (auto to : g[v]) {
		if (to != p) {
			id[to] = get(v, to);
			dfs(to, v);
		}
	}
	tout[v] = tmr;
}
bool upper(int x, int y) {
	return tin[x] <= tin[y] && tout[y] <= tout[x];
}
int lca(int x, int y, int ok = 0) {
	if (upper(x, y)) return x;
	if (upper(y, x)) return y;
	if (ok == 2) swap(x, y);
	for (int i = 19; i >= 0; i--) {
		if (up[x][i] && !upper(up[x][i], y)) {
			x = up[x][i];
		}
	}
	if (ok) return id[x];
	return up[x][0];
}
int getID(int v, int u) {
	for (int i = 19; i >= 0; i--) {
		if (up[v][i] && !upper(up[v][i], u)) {
			v = up[v][i];
		}
	}
	return id[v];
}

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 nxt(int v) {
	if (p[v] == v) return v;
	return p[v] = nxt(p[v]);
}

void go(int v, int u, int type) {
	int laste = -1, lastv = -1;
	while (lvl[v] > lvl[u]) {
		int cur = id[v];
		if (laste != -1) {
			if (type == 1) {
				g1[cur].pb(laste);
				g1[laste].pb(cur);
			}
			else {
				g2[cur].pb(laste);
				g2[laste].pb(cur);
			}
			p[lastv] = v;
		}
		laste = cur;
		lastv = v;
		v = up[nxt(v)][0];
	}
}
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 <= n; i++) {
		p[i] = i;
	}
	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);
			go(x, y, 1);
		}
		else {
			go(x, batya, 1);
			go(y, batya, 2);
			int last1 = getID(x, batya), last2 = getID(y, batya);
			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:145: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:148: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:158: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
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 83896 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 379 ms 109232 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 70424 KB Output is correct
2 Correct 16 ms 70556 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 70424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 70820 KB Output is correct
2 Correct 16 ms 70820 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 70820 KB Output is correct
2 Correct 29 ms 70820 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 793 ms 98700 KB Output is correct
2 Correct 803 ms 99912 KB Output is correct
3 Correct 496 ms 90176 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 936 ms 101144 KB Output is correct
2 Correct 846 ms 100920 KB Output is correct
3 Correct 543 ms 91816 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 799 ms 100764 KB Output is correct
2 Correct 683 ms 99132 KB Output is correct
3 Correct 569 ms 91364 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 876 ms 101084 KB Output is correct
2 Correct 843 ms 100740 KB Output is correct
3 Correct 476 ms 91412 KB Output is correct