| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 570443 |
2022-05-29T23:56:21 Z |
aryan12 |
Usmjeri (COCI17_usmjeri) |
C++17 |
|
788 ms |
105456 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<int> g[N];
vector<array<int, 2> > g2[N];
int dp[19][N];
int color[N];
bool vis[N];
void dfs(int node, int par)
{
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);
}
}
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++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
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]);
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);
int ans = 1;
for(int i = 2; i <= n; i++)
{
if(!vis[i])
{
ans = (ans * 2) % MOD;
}
if(!vis[i] && !dfs_check(i, 1))
{
cout << "0\n";
return;
}
}
cout << ans << "\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 |
93 ms |
45868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
105456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
14804 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14804 KB |
Output is correct |
| 2 |
Correct |
10 ms |
15088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15700 KB |
Output is correct |
| 2 |
Correct |
10 ms |
15724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15700 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
343 ms |
82976 KB |
Output is correct |
| 2 |
Correct |
342 ms |
93680 KB |
Output is correct |
| 3 |
Correct |
283 ms |
66384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
788 ms |
91456 KB |
Output is correct |
| 2 |
Correct |
710 ms |
91188 KB |
Output is correct |
| 3 |
Correct |
371 ms |
67404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
604 ms |
92224 KB |
Output is correct |
| 2 |
Correct |
313 ms |
83852 KB |
Output is correct |
| 3 |
Correct |
492 ms |
73120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
577 ms |
92588 KB |
Output is correct |
| 2 |
Correct |
505 ms |
101300 KB |
Output is correct |
| 3 |
Correct |
263 ms |
66240 KB |
Output is correct |
