| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 35388 |
2017-11-21T15:54:20 Z |
RockyB |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
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] = 1;
dfs1(to);
}
else if (clr[to] != 1) cout << 0, ioi
}
for (auto to : g2[v]) {
if (!was[to]) {
clr[to] = 2;
dfs1(to);
}
else if (clr[to] != 2) 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:87: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:90: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:97: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 |
Memory limit exceeded |
1679 ms |
262144 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Memory limit exceeded |
1626 ms |
262144 KB |
Memory limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
43468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
43468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
43864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
43864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
215672 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
262144 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
262144 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2000 ms |
183884 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
