oj.uz

Submission #87521

# Submission time Handle Problem Language Result Execution time Memory
87521 2018-12-01T03:20:27 Z mirbek01 Pictionary (COCI18_pictionary) C++17
140 / 140
 695 ms 44044 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, q, par[N], sz[N];
int p[20][N], mn[20][N], tin[N], tout[N], timer;
vector < pair <int, int> > v[N], g[N];

int get(int v){
      return (par[v] == v) ? v : par[v] = get(par[v]);
}

void unite(int a, int b){
      if(sz[a] < sz[b])
            swap(a, b);
      par[b] = a;
      sz[a] += sz[b];
}

void dfs(int v, int pr = 0, int we = 0){
      tin[v] = ++ timer;
      p[0][v] = pr;
      mn[0][v] = we;
      for(int i = 1; i < 20; i ++){
            p[i][v] = p[i - 1][ p[i - 1][v] ];
            mn[i][v] = min(mn[i - 1][v], mn[i - 1][ p[i - 1][v] ]);
      }
      for(int i = 0; i < g[v].size(); i ++){
            int to = g[v][i].first, w = g[v][i].second;
            if(to == pr) continue;
            dfs(to, v, w);
      }
      tout[v] = timer;
}

bool upper(int a, int b){
      return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int main(){
      scanf("%d %d %d", &n, &m, &q);

      for(int i = 1; i <= n; i ++)
            par[i] = i, sz[i] = 1;

      for(int i = 1; i <= m; i ++){
            for(int j = i + i; j <= n; j += i){
                  v[__gcd(i, j)].push_back({i, j});
            }
      }

      for(int i = m; i >= 1; i --){
            for(int j = 0; j < v[i].size(); j ++){
                  int a = v[i][j].first, b = v[i][j].second;
                  if(get(a) != get(b)){
                        g[a].push_back({b, i});
                        g[b].push_back({a, i});
                        unite(get(a), get(b));
                  }
            }
      }

      dfs(1);

      while(q --){
            int a, b, ans = 1e9;
            cin >> a >> b;
            if(!upper(a, b)){
                  for(int i = 19; i >= 0; i --){
                        if(p[i][a] && !upper(p[i][a], b)){
                              ans = min(ans, mn[i][a]);
                              a = p[i][a];
                        }
                  }
                  ans = min(ans, mn[0][a]);
            }
            if(!upper(b, a)){
                  for(int i = 19; i >= 0; i --){
                        if(p[i][b] && !upper(p[i][b], a)){
                              ans = min(ans, mn[i][b]);
                              b = p[i][b];
                        }
                  }
                  ans = min(ans, mn[0][b]);
            }
            cout << m - ans + 1 << endl;
      }
}

Compilation message

pictionary.cpp: In function 'void dfs(int, int, int)':
pictionary.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < g[v].size(); i ++){
                      ~~^~~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < v[i].size(); j ++){
                            ~~^~~~~~~~~~~~~
pictionary.cpp:43:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d", &n, &m, &q);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5624 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5704 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 6628 KB Output is correct
2 Correct 183 ms 7232 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 8424 KB Output is correct
2 Correct 256 ms 8424 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 14984 KB Output is correct
2 Correct 179 ms 15308 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 18372 KB Output is correct
2 Correct 250 ms 19380 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 23700 KB Output is correct
2 Correct 235 ms 24952 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 25920 KB Output is correct
2 Correct 441 ms 32044 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 34832 KB Output is correct
2 Correct 615 ms 39096 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 43232 KB Output is correct
2 Correct 624 ms 44044 KB Output is correct