| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35462 |
2017-11-22T05:37:58 Z |
RockyB |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
929 ms |
109240 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 laste = -1, lastv = -1;
while (lvl[v] > lvl[u]) {
int cur = id[v];
if (laste != -1) {
g1[cur].pb(laste);
g1[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);
}
else {
go(x, batya);
go(y, batya);
int last1 = lca(x, y, 1), last2 = lca(x, y, 2);
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:139: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:142: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:152:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &x, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
83892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
293 ms |
109240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
70424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
70556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
70424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
70556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
70820 KB |
Output is correct |
| 2 |
Correct |
13 ms |
70820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
70820 KB |
Output is correct |
| 2 |
Correct |
16 ms |
70820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
679 ms |
98696 KB |
Output is correct |
| 2 |
Correct |
766 ms |
99868 KB |
Output is correct |
| 3 |
Correct |
479 ms |
90184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
929 ms |
101164 KB |
Output is correct |
| 2 |
Correct |
903 ms |
100936 KB |
Output is correct |
| 3 |
Correct |
596 ms |
91820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
889 ms |
100780 KB |
Output is correct |
| 2 |
Correct |
749 ms |
99124 KB |
Output is correct |
| 3 |
Correct |
623 ms |
91372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
796 ms |
101116 KB |
Output is correct |
| 2 |
Correct |
846 ms |
100792 KB |
Output is correct |
| 3 |
Correct |
456 ms |
91412 KB |
Output is correct |
