Submission #83141

#	Time	Username	Problem	Language	Result	Execution time	Memory
83141		wjoao	Usmjeri (COCI17_usmjeri)	C++11	28 / 140	344 ms	72904 KiB

usmjeri

#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 (stderr)

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);
     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14