| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 83141 |
2018-11-05T15:03:00 Z |
wjoao |
Usmjeri (COCI17_usmjeri) |
C++11 |
|
344 ms |
72904 KB |
#include<bits/stdc++.h>
#define vi vector<int>
#define maxn 300010
#define maxlogn 20
#define mod 1000000007
using namespace std;
vi g[maxn];
int n, m, a, b, father[maxn], color[maxn];
class BinaryLifting{ public:
int table[maxn][maxlogn];
int prof[maxn];
int tam;
BinaryLifting(){
memset(table, -1, sizeof table);
}
// a profundidade
// a posição [i][0] deve está preenchida.(Os pais dos nós)
void build(int n){
int i, j, aux;
tam = n;
for(j = 1; j < maxlogn; j++){
for(i = 0; i < n; i++){
aux = table[i][j-1];
if( aux != -1 ) aux = table[aux][j-1];
table[i][j] = aux;
}
}
}
int up(int a, int d){
for(int i = 0; i < maxlogn; i++){
if( d & (1 << i) ){
a = table[a][i];
}
}
return a;
}
int lca(int a, int b){
if( prof[a] < prof[b] ) b = up(b, prof[b]-prof[a]);
else if( prof[b] < prof[a] ) a = up(a, prof[a]-prof[b]);
if( a == b ) return a;
for(int i = maxlogn-1; i >= 0; i--){
if( table[a][i] != table[b][i] ){
a = table[a][i];
b = table[b][i];
}
}
return table[a][0];
}
} lca;
struct UnionFind{
int pai[maxn];
UnionFind(){
memset(pai, -1, sizeof pai);
}
int find(int i){
if(pai[i] == -1) return i;
pai[i] = find(pai[i]);
return pai[i];
}
bool uni(int x, int y){
if(lca.prof[x] > lca.prof[y] ) swap(x,y);
if(find(x) == find(y)) return false;
pai[find(y)] = find(x);
return true;
}
} uf;
/*
-1 se impossivel.
0 se qualquer cor.
1 ou 2 se cor definida.
*/
int getfcolor(int v, int p, int cor){
int u = uf.find(v);
if(cor != 0 && cor != color[u]) return -1;
cor = color[u];
if(lca.prof[u] > lca.prof[p]) return getfcolor(father[u], p, cor);
return cor;
}
void setcolor(int v, int p, int cor){
int u = uf.find(v);
uf.uni(u, p);
color[u] = cor;
if(lca.prof[u] > lca.prof[p]) setcolor(father[u], p, cor);
}
void make_root(int v, int p = 1){
lca.prof[v] = p;
for(int i = 0; i < g[v].size(); i++){
int u = g[v][i];
if(lca.prof[u] == 0){
father[u] = v;
lca.table[u][0] = v;
make_root(u, p+1);
}
}
}
int main(){
scanf(" %d %d", &n, &m);
for(int i = 0; i < n-1; i++){
scanf(" %d %d", &a, &b);
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
father[0] = -1;
make_root(0);
lca.build(n);
bool impossivel = false;
for(int i = 0; i < m; i++){
//cout << i << endl;
scanf(" %d %d", &a, &b);
a--; b--;
int p = lca.lca(a,b);
//cout << i << " p: " << p << " " << a << " " << b << endl;
if(b == p) swap(a,b);
if(a == p){
int cora = getfcolor(b, p, 0);
if(cora == -1){
impossivel = true;
break;
}
setcolor(b, p, cora);
}else{
int cora = getfcolor(a, p, 0);
int corb = getfcolor(b, p, 0);
if(cora == -1 || corb == -1 || (cora != 0 && cora == corb)){
impossivel = true;
break;
}else if( cora == 0 && corb == 0){
setcolor(a, p, 1);
setcolor(b, p, 2);
} else if( cora != 0 && corb != 0){
setcolor(a, p, cora);
setcolor(b, p, corb);
} else if(cora == 0 && corb != 0 ){
if(corb == 1) cora = 2;
if(corb == 2) cora = 1;
setcolor(a, p, cora);
setcolor(b, p, corb);
} else if(corb == 0 && cora != 0){
if(cora == 1) corb = 2;
if(cora == 2) corb = 1;
setcolor(a, p, cora);
setcolor(b, p, corb);
}
}
}
if(impossivel){
printf("0\n");
}else{
int c = 0;
for(int i = 0; i < n; i++){
if(uf.find(i) == i) c++;
}
long long res = 1;
while(c){
res <<= 1LL;
res %= mod;
c--;
}
printf("%lld\n", res);
}
}
Compilation message
usmjeri.cpp: In function 'void make_root(int, int)':
usmjeri.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~~
usmjeri.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~
usmjeri.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
44024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
344 ms |
68472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
343 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
68472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
304 ms |
72904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
