| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 570442 |
2022-05-29T23:54:25 Z |
aryan12 |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
830 ms |
119532 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5, M = 3e5 + 5, MOD = 1e9 + 7;
int depth[N], min_depth[N];
vector<array<int, 3> > special_pairs(M);
vector<int> g[N];
vector<array<int, 2> > g2[N];
int dp[19][N];
int tin[N], tout[N], tim = 0;
int parent[N], color[N];
bool vis[N];
int power(int a, int b)
{
if(b == 0) return 1;
if(b == 1) return a;
int x = power(a, b / 2);
x = (x * x) % MOD;
if(b & 1)
{
x = (x * a) % MOD;
}
return x;
}
void dfs(int node, int par)
{
tin[node] = ++tim;
dp[0][node] = par;
for(int to: g[node])
{
if(to == par) continue;
depth[to] = depth[node] + 1;
min_depth[to] = depth[to];
dfs(to, node);
}
tout[node] = ++tim;
}
int Find(int x)
{
if(x == parent[x]) return x;
return parent[x] = Find(parent[x]);
}
void Unite(int x, int y)
{
x = Find(x), y = Find(y);
parent[x] = y;
}
int LCA(int x, int y)
{
if(depth[x] > depth[y]) swap(x, y);
int diff = depth[y] - depth[x];
for(int i = 18; i >= 0; i--)
{
if(diff & (1 << i))
{
y = dp[i][y];
}
}
if(x == y) return x;
for(int i = 18; i >= 0; i--)
{
if(dp[i][x] != dp[i][y])
{
x = dp[i][x];
y = dp[i][y];
}
}
return dp[0][x];
}
void again_dfs(int node, int par)
{
for(int to: g[node])
{
if(to == par) continue;
// cout << "to = " << to << ", node = " << node << "\n";
again_dfs(to, node);
min_depth[node] = min(min_depth[node], min_depth[to]);
if(min_depth[to] < depth[node])
{
// cout << to << " <-> " << node << " with 0\n";
g2[to].push_back({node, 0});
g2[node].push_back({to, 0});
}
}
}
bool dfs_check(int node, int cur_color)
{
vis[node] = true;
if(color[node] == 0 || color[node] == cur_color)
{
color[node] = cur_color;
}
if(color[node] != cur_color) return false;
for(auto [to, wt]: g2[node])
{
int next_color = (wt == 0) ? cur_color : 3 - cur_color;
if(color[to] != 0 && color[to] != next_color) return false;
if(vis[to]) continue;
if(!dfs_check(to, next_color)) return false;
}
return true;
}
void Solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i < n; i++)
{
parent[i] = i;
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
parent[n] = n;
depth[1] = 0;
min_depth[1] = 0;
dfs(1, -1);
for(int i = 1; i < 19; i++)
{
for(int j = 1; j <= n; j++)
{
if(dp[i - 1][j] == -1)
{
dp[i][j] = -1;
}
else
{
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
int lca = LCA(u, v);
min_depth[u] = min(min_depth[u], depth[lca]);
min_depth[v] = min(min_depth[v], depth[lca]);
special_pairs[i] = {u, lca, v};
if(lca != u && lca != v)
{
g2[u].push_back({v, 1});
g2[v].push_back({u, 1});
// cout << u << " <-> " << v << " with 1\n";
}
}
again_dfs(1, -1);
for(int i = 1; i <= m; i++)
{
// cout << special_pairs[i][0] << " " << special_pairs[i][1] << " " << special_pairs[i][2] << "\n";
int cur = special_pairs[i][0];
cur = Find(cur);
while(depth[cur] > depth[special_pairs[i][1]])
{
Unite(cur, dp[0][cur]);
cur = Find(cur);
}
cur = special_pairs[i][2];
cur = Find(cur);
while(depth[cur] > depth[special_pairs[i][1]])
{
Unite(cur, dp[0][cur]);
cur = Find(cur);
}
}
int components = 0;
for(int i = 1; i <= n; i++)
{
if(Find(i) == i)
{
components++;
}
}
for(int i = 2; i <= n; i++)
{
if(!vis[i] && !dfs_check(i, 1))
{
cout << "0\n";
return;
}
}
cout << power(2LL, components) << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
55292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
236 ms |
119532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
22980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
22932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
99972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
830 ms |
108408 KB |
Output is correct |
| 2 |
Correct |
793 ms |
108568 KB |
Output is correct |
| 3 |
Correct |
442 ms |
82440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
711 ms |
109368 KB |
Output is correct |
| 2 |
Incorrect |
371 ms |
101072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
733 ms |
109888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
