Submission #93534

#	Time	Username	Problem	Language	Result	Execution time	Memory
93534		Milki	Pictionary (COCI18_pictionary)	C++14	140 / 140	467 ms	5488 KiB

pictionary

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14