| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 763473 |
2023-06-22T10:58:04 Z |
fanwen |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
357 ms |
82380 KB |
/**
* author : pham van sam
* created : 22 June 2023 (Thursday)
**/
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <typename U, typename V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <typename U, typename V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
const int MAXN = 3e5 + 5;
int N, M, depth[MAXN], anc[MAXN][20], Min[MAXN];
vector <int> adj[MAXN];
void dfs(int u, int p) {
anc[u][0] = p;
depth[u] = Min[u] = depth[p] + 1;
FOR(i, 1, 19) anc[u][i] = anc[anc[u][i - 1]][i - 1];
for (auto v : adj[u]) if(v != p) {
dfs(v, u);
}
}
int lca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
FORD(i, 19, 0) if(depth[anc[u][i]] >= depth[v]) {
u = anc[u][i];
}
FORD(i, 19, 0) if(anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
while(u != v) {
u = anc[u][0];
v = anc[v][0];
// cout << u << " " << v << '\n';
}
return u;
}
vector <pair <int, int>> ke[MAXN];
void add_edges(int u, int v, int c) {
ke[u].emplace_back(v, c);
ke[v].emplace_back(u, c);
}
void DFS(int u, int p) {
for (auto v : adj[u]) if(v != p) {
DFS(v, u);
minimize(Min[u], Min[v]);
if(Min[v] < depth[u]) add_edges(u, v, 0);
}
}
int used[MAXN];
bool calc(int u, int c) {
if(used[u] != -1) return used[u] == c;
used[u] = c;
for (auto [v, x] : ke[u]) {
if(!calc(v, x ^ c)) return false;
}
return true;
}
void process(void) {
cin >> N >> M;
FOR(i, 2, N) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
while(M--) {
int u, v; cin >> u >> v;
int x = lca(u, v);
minimize(Min[u], depth[x]);
minimize(Min[v], depth[x]);
if(x != u && x != v) add_edges(u, v, 1);
}
DFS(1, 0);
memset(used, -1, sizeof used);
int res = 1, Mod = 1e9 + 7;
FOR(i, 2, N) if(used[i] == -1) {
if(!calc(i, 0)) return void(cout << 0);
(res *= 2) %= Mod;
}
cout << res;
}
signed main() {
#define TASK "usmjeri"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
auto start_time = steady_clock::now();
int test = 1;
// cin >> test;
for (int i = 1; i <= test; ++i) {
process();
// cout << '\n';
}
auto end_time = steady_clock::now();
cerr << "\nExecution time : " << duration_cast<milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
39408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
234 ms |
82380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15724 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15720 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16340 KB |
Output is correct |
| 2 |
Correct |
10 ms |
16200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
16312 KB |
Output is correct |
| 2 |
Correct |
11 ms |
16416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
61952 KB |
Output is correct |
| 2 |
Correct |
357 ms |
63780 KB |
Output is correct |
| 3 |
Correct |
177 ms |
46560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
354 ms |
65996 KB |
Output is correct |
| 2 |
Correct |
331 ms |
65876 KB |
Output is correct |
| 3 |
Correct |
227 ms |
50388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
339 ms |
66636 KB |
Output is correct |
| 2 |
Correct |
331 ms |
62888 KB |
Output is correct |
| 3 |
Correct |
221 ms |
50376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
338 ms |
67056 KB |
Output is correct |
| 2 |
Correct |
340 ms |
67528 KB |
Output is correct |
| 3 |
Correct |
218 ms |
47152 KB |
Output is correct |
