oj.uz

Submission #93534

# Submission time Handle Problem Language Result Execution time Memory
93534 2019-01-09T12:01:42 Z Milki Pictionary (COCI18_pictionary) C++14
140 / 140
 467 ms 5488 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 1e5 + 5, LOG = 20;

int n, m, q;
int par[MAXN], lo[MAXN], hi[MAXN];
vector <point> v;

int f(int x){
  if(par[x] == x) return x;
  return par[x] = f(par[x]);
}

void spoji(int x, int y){
  x = f(x); y = f(y);
  if(x == y) return;
  par[y] = x;
}

bool cmp(point A, point B){
  return A.first < B.first;
}

void merge(int x){
  int add = x; x += add;
  for( ; x <= n; x += add)
    spoji(x - add, x);
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> m >> q;
  REP(i, q){
    int a, b; cin >> a >> b;
    v.pb(point(a, b));
    lo[i] = 1; hi[i] = m;
  }

  REP(i, LOG){
    vector <point> vv;
    REP(j, q){
      int mid = (lo[j] + hi[j]) >> 1;
      vv.pb(point(mid, j));
    }
    sort(vv.begin(), vv.end(), cmp);

    FOR(i, 1, n + 1)
      par[i] = i;
    int solved = 0;

    for(auto it : vv){
      while(it.first > solved) { merge(m - solved); solved ++; }

      int id = it.second;
      int x = f(v[id].first), y = f(v[id].second);

      if( x == y )
        hi[id] = it.first;
      else
        lo[id] = it.first + 1;
    }
  }
  REP(i, q)
    cout << lo[i] << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1248 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3600 KB Output is correct
2 Correct 134 ms 3712 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 4696 KB Output is correct
2 Correct 178 ms 4400 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 2644 KB Output is correct
2 Correct 138 ms 2564 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 2684 KB Output is correct
2 Correct 168 ms 2940 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 4048 KB Output is correct
2 Correct 188 ms 2764 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 4740 KB Output is correct
2 Correct 326 ms 4760 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 4912 KB Output is correct
2 Correct 405 ms 4972 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 5488 KB Output is correct
2 Correct 467 ms 5380 KB Output is correct