| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 886941 |
2023-12-13T08:11:29 Z |
vjudge1 |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
968 ms |
131056 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;
}
struct DSU {
int n, *par;
DSU(int n) : n(n) {
// 23 orz
par = new int[n + 5];
iota(par, par + n + 5, 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) { // u -> 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;
map <int, pair <int, int>> redges;
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;
redges[i] = mp(u, v);
}
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), zipzip(n +1);
function <void(int, int)> merge = [&](int node, int par) -> void {
vector <int> vec;
vec.emplace_back(edges[mp(node, p[0][node])]);
node = zipzip.get(node);
while(depth[node] > depth[par]) {
vec.emplace_back(edges[mp(node, p[0][node])]);
if(p[0][node] != par) {
vec.emplace_back(edges[mp(p[0][node], p[1][node])]);
}
node = p[0][node];
node = zipzip.get(node);
}
for(int i = 0; i +1 < int(vec.size()); i++) {
dsu.unite(vec[i], vec[i +1]);
bdj[vec[i]].emplace_back(vec[i +1], 0);
bdj[vec[i +1]].emplace_back(vec[i], 0);
}
for(int i = 0; i < int(vec.size()); i++) {
auto [a, b] = redges[vec[i]];
if(depth[a] < depth[b]) {
swap(a, b);
}
zipzip.unite(a, b);
}
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) {
merge(a, c);
}
if(b != c) {
merge(b, c);
}
if(a != c && b != c) {
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(child, node);
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:210:26: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
210 | if(colors[i] != colors[child] ^ c) {
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
194 ms |
74668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
131056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
43868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
43864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
44892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
44888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
678 ms |
107440 KB |
Output is correct |
| 2 |
Correct |
767 ms |
118232 KB |
Output is correct |
| 3 |
Correct |
498 ms |
89872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
960 ms |
111316 KB |
Output is correct |
| 2 |
Correct |
878 ms |
118612 KB |
Output is correct |
| 3 |
Incorrect |
636 ms |
95088 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
814 ms |
111444 KB |
Output is correct |
| 2 |
Correct |
871 ms |
116896 KB |
Output is correct |
| 3 |
Correct |
631 ms |
94860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
968 ms |
112212 KB |
Output is correct |
| 2 |
Correct |
787 ms |
120148 KB |
Output is correct |
| 3 |
Correct |
577 ms |
91732 KB |
Output is correct |
