| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 376545 |
2021-03-11T16:42:38 Z |
SavicS |
Usmjeri (COCI17_usmjeri) |
C++14 |
|
537 ms |
83948 KB |
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 300005;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n, m;
vector<int> g[maxn];
int d[maxn];
int low[maxn];
int deda[maxn][20];
void dfs1(int v, int p){
low[v] = d[v];
deda[v][0] = p;
ff(i,1,19)deda[v][i] = deda[deda[v][i - 1]][i - 1];
for(auto u : g[v]){
if(u != p){
d[u] = d[v] + 1;
dfs1(u, v);
}
}
}
int lca(int x, int y){
if(d[x] < d[y])swap(x, y);
fb(i,19,0){
if((d[x] - d[y]) & (1 << i))x = deda[x][i];
}
fb(i,19,0){
if(deda[x][i] != deda[y][i]){
x = deda[x][i];
y = deda[y][i];
}
}
return (x == y ? x : deda[x][0]);
}
vector<pii> e[maxn];
void add_edge(int x, int y, int z){
e[x].pb({y, z});
e[y].pb({x, z});
}
int mn[maxn];
void dfs2(int v, int p){
mn[v] = low[v];
for(auto u : g[v]){
if(u != p){
dfs2(u, v);
if(mn[u] < d[v])add_edge(u, v, 0);
mn[v] = min(mn[v], mn[u]);
}
}
}
bool bip = 0;
int boja[maxn];
bool visited[maxn];
void dfs3(int v, int clr){
visited[v] = 1;
boja[v] = clr;
for(auto c : e[v]){
int u = c.fi;
int w = c.se;
if(!visited[u]){
dfs3(u, clr ^ w);
}
else{
if(boja[u] != clr ^ w)bip = 1;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
cin >> n >> m;
ff(i,1,n - 1){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs1(1, -1);
ff(i,1,n)low[i] = d[i];
ff(i,1,m){
int a, b;
cin >> a >> b;
int c = lca(a, b);
low[a] = min(low[a], d[c]);
low[b] = min(low[b], d[c]);
if(c != a && c != b)add_edge(a, b, 1);
}
dfs2(1, -1);
ll rez = 1;
ff(i,2,n){
if(!visited[i]){
dfs3(i, 0);
if(bip == 1)return cout << 0, 0;
rez = (rez * 2) % mod;
}
}
cout << rez << endl;
return 0;
}
/**
// probati bojenje sahovski ili slicno
**/
Compilation message
usmjeri.cpp: In function 'void dfs3(int, int)':
usmjeri.cpp:92:15: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
92 | if(boja[u] != clr ^ w)bip = 1;
| ~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
39552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
335 ms |
83948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
14572 KB |
Output is correct |
| 2 |
Correct |
11 ms |
14720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
15340 KB |
Output is correct |
| 2 |
Correct |
16 ms |
15232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
15340 KB |
Output is correct |
| 2 |
Correct |
13 ms |
15212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
473 ms |
63620 KB |
Output is correct |
| 2 |
Correct |
486 ms |
65388 KB |
Output is correct |
| 3 |
Correct |
271 ms |
47340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
524 ms |
67880 KB |
Output is correct |
| 2 |
Correct |
484 ms |
67564 KB |
Output is correct |
| 3 |
Correct |
353 ms |
51128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
68280 KB |
Output is correct |
| 2 |
Correct |
510 ms |
64492 KB |
Output is correct |
| 3 |
Correct |
345 ms |
51056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
537 ms |
68844 KB |
Output is correct |
| 2 |
Correct |
490 ms |
69116 KB |
Output is correct |
| 3 |
Correct |
360 ms |
47980 KB |
Output is correct |
