oj.uz

Submission #83149

# Submission time Handle Problem Language Result Execution time Memory
83149 2018-11-05T18:53:19 Z wjoao Pictionary (COCI18_pictionary) C++11
70 / 140
 1500 ms 11792 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2856 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 3876 KB Output is correct
2 Correct 98 ms 4556 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 5708 KB Output is correct
2 Correct 183 ms 6312 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1070 ms 7472 KB Output is correct
2 Correct 1058 ms 7996 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 8924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 9260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 11076 KB Output is correct
2 Execution timed out 1572 ms 11076 KB Time limit exceeded

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1566 ms 11084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1573 ms 11792 KB Time limit exceeded
2 Halted 0 ms 0 KB -