Submission #93547

#	Time	Username	Problem	Language	Result	Execution time	Memory
93547		patrikpavic2	Pictionary (COCI18_pictionary)	C++17	140 / 140	814 ms	47420 KiB

pictionary

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <queue>

#define PB push_back
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int, int> pii;
typedef pair < ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vl;
typedef pair < pii, pii > edg;

const int N = 5e5 + 500;
const int M = 2e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 20;
const int OFF = (1 << LOG);
const double EPS = 1e-9;
const double PI = 3.1415926535;

int lo[N], hi[N], koji[N], pr[N], a[M], b[M], c[M], a2[N], b2[N], n, q, m;
vector < edg > v;

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

void mrg(int x,int y){
    x = par(x), y = par(y);
    pr[x] = y;
}

void iterrate(){
    for(int i = 1;i<=n;i++) pr[i] = i;
    vector < edg > qq;

    for(int i = 1;i<=q;i++){
        if(lo[i] == hi[i]) continue;
        qq.PB({{(lo[i] + hi[i] + 1) / 2, i}, {a2[i], b2[i]}});
    }
    sort(qq.begin(), qq.end());
    int j = 0;
    for(int i = 0;i<v.size();i++){
        while(j < qq.size() && v[i].X.X > qq[j].X.X){
            if(par(qq[j].Y.X) != par(qq[j].Y.Y)){
                lo[qq[j].X.Y] = qq[j].X.X;
            }
            else{
                hi[qq[j].X.Y] = qq[j].X.X - 1;
            }
            j++;
        }
        mrg(v[i].Y.X, v[i].Y.Y);
    }
   while(j < qq.size()){
        if(par(qq[j].Y.X) != par(qq[j].Y.Y)){
            lo[qq[j].X.Y] = qq[j].X.X;
        }
        else{
            hi[qq[j].X.Y] = qq[j].X.X - 1;
        }
        j++;
    }
}

int main(){
    scanf("%d%d%d",&n,&m, &q);
    for(int i = 1;i<=q;i++){
        scanf("%d%d", a2 + i, b2 + i);
        lo[i] = 0, hi[i] = N;
    }
    int cr = 0;
    for(int i = 1;i<=m;i++){
        for(int j = 2 * i;j <= n;j += i){
            a[cr] = i;b[cr] = j;c[cr] = m - i + 1;
            cr++;
        }
    }
    m = cr;
    for(int i = 0;i<m;i++){
        v.PB({{c[i], INF}, {a[i], b[i]}});
    }
    sort(v.begin(), v.end());
    for(int i = 0;i<20;i++) iterrate();
    ll sol = 0;
    for(int i = 1;i<=q;i++){
        printf("%d\n", lo[i] + 1);
    }
    return 0;
}

Compilation message (stderr)

pictionary.cpp: In function 'void iterrate()':
pictionary.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++){
                   ~^~~~~~~~~
pictionary.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < qq.size() && v[i].X.X > qq[j].X.X){
               ~~^~~~~~~~~~~
pictionary.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j < qq.size()){
          ~~^~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:101:8: warning: unused variable 'sol' [-Wunused-variable]
     ll sol = 0;
        ^~~
pictionary.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
pictionary.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a2 + i, b2 + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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