| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 886928 |
2023-12-13T07:35:46 Z |
vjudge1 |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
2000 ms |
262144 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MOD = 1E9 + 7;
const int MAXN = 3E5 + 5;
const int LOG = 25;
int p[LOG][MAXN];
int depth[MAXN], tin[MAXN], tout[MAXN];
int get(int a, int b) {
for(int i = LOG -1; i >= 0; i--) {
if(b & (1 << i)) {
a = p[i][a];
}
}
return a;
}
int par[MAXN];
struct DSU {
int n;
DSU(int n) : n(n) {
// 23 orz
iota(par, par + n, 0);
}
int get(int x) {
if(par[x] == x) {
return x;
}
return par[x] = get(par[x]);
}
bool same(int a, int b) {
return get(a) == get(b);
}
bool unite(int u, int v) {
if(same(u, v)) {
return false;
}
u = get(u);
v = get(v);
par[u] = v;
return true;
}
};
int lca(int a, int b) {
if(depth[a] > depth[b]) {
swap(a, b);
}
b = get(b, depth[b] - depth[a]);
if(a == b) {
return a;
}
for(int lg = LOG -1; lg >= 0; lg--) {
if(p[lg][a] != p[lg][b]) {
a = p[lg][a];
b = p[lg][b];
}
}
return p[0][a];
}
vector <pair <int, int>> adj[MAXN];
vector <pair <int, int>> bdj[MAXN];
map <pair <int, int>, int> edges;
pair <int, int> mp(int a, int b) {
return {min(a, b), max(a, b)};
}
#define ONLINE_JUDGE
void solve() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= n -1; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
edges[mp(u, v)] = i;
}
int timer = 0;
function <void(int, int)> dfs = [&](int node, int par) -> void {
tin[node] = timer++;
p[0][node] = par;
depth[node] = depth[par] +1;
for(auto &[child, col] : adj[node]) {
if(child != par) {
dfs(child, node);
}
}
tout[node] = timer++;
};
dfs(1, 0);
for(int lg = 1; lg < LOG; lg++) {
for(int i = 1; i <= n; i++) {
p[lg][i] = p[lg -1][p[lg -1][i]];
}
}
DSU dsu(n +1);
function <void(int, int)> merge = [&](int node, int par) -> void {
vector <int> vec;
while(node != par) {
assert(edges.count(mp(node, p[0][node])));
assert(edges.count(mp(node, p[0][node])));
vec.emplace_back(edges[mp(node, p[0][node])]);
node = p[0][node];
}
for(int i = 0; i +1 < int(vec.size()); i++) {
bdj[vec[i]].emplace_back(vec[i +1], 0);
bdj[vec[i +1]].emplace_back(vec[i], 0);
}
return;
};
vector <array <int, 3>> queries(m +1);
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
int c = lca(a, b);
queries[i] = {a, b, c};
if(a != c) {
assert(tin[c] < tin[a] && tout[a] < tout[c]);
merge(a, c);
}
if(b != c) {
assert(tin[c] < tin[b] && tout[b] < tout[c]);
merge(b, c);
}
if(a != c && b != c) {
assert(tin[c] < min(tin[a], tin[b]) && max(tout[a], tout[b]) < tout[c]);
assert(edges.count(mp(a, p[0][a])));
assert(edges.count(mp(b, p[0][b])));
bdj[edges[mp(a, p[0][a])]].emplace_back(edges[mp(b, p[0][b])], 1);
bdj[edges[mp(b, p[0][b])]].emplace_back(edges[mp(a, p[0][a])], 1);
}
}
vector <int> colors(n +1, -1);
function <void(int, int, int)> paint = [&](int node, int par, int col) -> void {
if(colors[node] != -1) {
if(colors[node] != col) {
cerr << node << " " << par << "\n";
cout << 0;
exit(0);
}
return;
}
colors[node] = col;
for(auto [child, c] : bdj[node]) {
if(child != par) {
dsu.unite(node, child);
paint(child, node, col ^ c);
}
}
return;
};
for(int i = 1; i <= n -1; i++) {
if(colors[i] == -1) {
paint(i, 0, 0);
}
}
for(int i = 1; i <= n -1; i++) {
for(auto [child, c] : bdj[i]) {
if(colors[i] != colors[child] ^ c) {
cerr << i << " " << child << " -> " << colors[i] << " " << colors[child] << " :: " << c << "\n";
cout << 0;
exit(0);
}
}
}
int ans = 1;
for(int i = 1; i <= n -1; i++) {
if(dsu.get(i) == i) {
ans = (ans * 2) % MOD;
}
}
cout << ans;
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
Compilation message
usmjeri.cpp: In function 'void solve()':
usmjeri.cpp:198:26: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
198 | if(colors[i] != colors[child] ^ c) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
233260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1895 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
45912 KB |
Output is correct |
| 2 |
Correct |
8 ms |
45912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
45916 KB |
Output is correct |
| 2 |
Correct |
8 ms |
46004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
46432 KB |
Output is correct |
| 2 |
Correct |
10 ms |
46680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
46612 KB |
Output is correct |
| 2 |
Correct |
11 ms |
46256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
199920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
182436 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2106 ms |
186748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2017 ms |
181360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
