oj.uz

Submission #102365

# Submission time Handle Problem Language Result Execution time Memory
102365 2019-03-24T13:56:31 Z ubiratan37 Pictionary (COCI18_pictionary) C++11
140 / 140
 108 ms 12076 KB 
#include <bits/stdc++.h>
 
#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector< ii >
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
const double PI = acos(-1);
 
using namespace std;
 
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
 
int gcd(int a, int b){
  if(a == 0) return b;
  else return gcd(b%a, a);
}
 
int uf[112345];
int sz[112345];
int mx[112345];
vector<int> g[112345];
int L[112345];
 
int find(int u){
  if(uf[u] == u) return u;
  else return find(uf[u]);
}
 
void init(int n, int m){
  for(int i=0; i<=n; i++){
    uf[i] = i;
    sz[i] = 1;
    mx[i] = 0;
  }
}
 
int maxl = 0;
 
void merge(int x, int y, int t){
  int a = find(x);
  int b = find(y);
  if(a == b) return;
  if(sz[a] < sz[b]) swap(a,b);
  uf[b] = a;
  sz[a] += sz[b];
  mx[b] = t;
}
  
void go(int u, int l, int p){
  L[u] = l;
  maxl = max(maxl, l);
  for(int v : g[u]){
    if(v != p){
      //cout << u << " -> " << v << endl;
      go(v, l+1, u);
    }
  }
}
 
int32_t main(){
  DESYNC;
  int n,m;
  cin >> n >> m;
  init(n,m);
  for(int i=m; i>=1; i--){
    for(int j=i; j<=n; j+=i){
      merge(i, j, m - i + 1);
    }
  }
  for(int i=1; i<=n; i++){
    //cout << "i + uf[i]" << i << " + " << uf[i] << endl;
    if(uf[i] != i){
      g[uf[i]].pb(i);
      g[i].pb(uf[i]);
    }
    //cout << mx[i] << " ";
  }
  //cout << endl;
  go(find(1), 1, -1);
  int q;
  cin >> q;
  while(q--){
    int ans = 0;
    int u,v;
    cin >> u >> v;
    if(u == v){
      cout << 0 << endl;
    }
    else {
      while(u != v){
        if(L[u] > L[v]){
          ans = max(ans, mx[u]);
          u = uf[u];
        }
        else {
          ans = max(ans, mx[v]);
          v = uf[v];
        }
      }
      //ans = max(ans, mx[u]);
      cout << ans << endl;
    }
  }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3072 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3072 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3320 KB Output is correct
2 Correct 20 ms 3968 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3448 KB Output is correct
2 Correct 33 ms 4332 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4856 KB Output is correct
2 Correct 31 ms 5368 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5504 KB Output is correct
2 Correct 32 ms 6428 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6648 KB Output is correct
2 Correct 44 ms 7312 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7620 KB Output is correct
2 Correct 69 ms 9428 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 9224 KB Output is correct
2 Correct 108 ms 11048 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 10660 KB Output is correct
2 Correct 100 ms 12076 KB Output is correct