Submission #83149

#	Time	Username	Problem	Language	Result	Execution time	Memory
83149		wjoao	Pictionary (COCI18_pictionary)	C++11	70 / 140	1573 ms	11792 KiB

pictionary

#include <bits/stdc++.h>
#define maxn 100010
#define pii pair<int, int>
#define vpii vector< pii >

using namespace std;

struct UnionFind{
  vpii pai[maxn];

  int find(int i, int t){
    vpii::iterator it = upper_bound(pai[i].begin(), pai[i].end(), make_pair(t, maxn*2));
    if(pai[i].size() == 0 || it == pai[i].begin()) return i;
    it--;
    if( it->second == i ) return i;
    return find(it->second, t);
  }

  void uni(int x, int y, int t){
    int px = find(x, t);
    int py = find(y, t);
    if(px == py) return;
    pai[py].push_back(make_pair(t, px));
  }

  void print(){
    for(int i = 0; i < 10; i++){
      cout << "V: " << i << "pares: ";
      for(int j = 0; j < pai[i].size(); j++){
        cout << " ; ("<< pai[i][j].first<< ", " << pai[i][j].second << ")";
      }
      cout << endl;
    }
  }

} uf;

int n, m, q, a, b;

void crivo(){
  for(int t = 1, m1 = m; m1 >= 1; m1--, t++){
    for(int j = m1*2; j <= n; j += m1){
      uf.uni(m1, j, t);
    }
  }
}

// 1 - Se o valor for maior.
// 0 - Se o valor for menor igual.
bool check(int a, int b, int i){
  return uf.find(a, i) != uf.find(b, i);
}

// a inicio e b é o final
// 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
int query(int _a, int _b, int a, int b){
	int meio = (a+b)/2LL;
	if( a == b ) return a;
	if( check(_a, _b, meio) ){
		return query(_a, _b, meio+1LL, b);
	}else{
		return query(_a, _b, a, meio);
	}
}

int main(){
  scanf(" %d %d %d", &n, &m, &q);
  crivo();
  for(int i = 0; i < q; i++){
    scanf(" %d %d", &a, &b);
    printf("%d\n", query(a, b, 1,m));
  }
  return 0;
}

Compilation message (stderr)

pictionary.cpp: In member function 'void UnionFind::print()':
pictionary.cpp:29:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j = 0; j < pai[i].size(); j++){
                      ~~^~~~~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d %d", &n, &m, &q);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:70: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: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14