Submission #87379

#	Time	Username	Problem	Language	Result	Execution time	Memory
87379		mirbek01	Pictionary (COCI18_pictionary)	C++17	56 / 140	1580 ms	28408 KiB

pictionary

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, q, ans[N], p[N], sz[N];
vector < pair <int, int> > v[N];
vector < tuple <int, int, int> > vec;

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

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

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

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

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

      for(int i = 1; i <= q; i ++){
            int u, v;
            cin >> u >> v;
            vec.push_back(make_tuple(u, v, i));
      }

      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;
                  unite(a, b);
            }
            for(int j = 0; j < vec.size(); j ++){
                  int a = get<0>(vec[j]);
                  int b = get<1>(vec[j]);
                  int c = get<2>(vec[j]);
                  if(!ans[c]){
                        if(get(a) == get(b)){
                              ans[c] = i;
                        }
                  }
            }
      }

      for(int i = 1; i <= q; i ++)
            cout << m - ans[i] + 1 << endl;
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:45:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < v[i].size(); j ++){
                            ~~^~~~~~~~~~~~~
pictionary.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < vec.size(); j ++){
                            ~~^~~~~~~~~~~~
pictionary.cpp:27: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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14