Submission #93554

#	Time	Username	Problem	Language	Result	Execution time	Memory
93554		BartolM	Pictionary (COCI18_pictionary)	C++17	140 / 140	447 ms	39388 KiB

pictionary

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;

const int INF=0x3f3f3f3f;
const int N=1e5+5;

int n, m, q;
pii queries[N], gran[N], gran2[N];
vector <int> v[N], vn[N]; //za svaki mid unutra je par <index, <lo, hi> >
vector <pii> dan[N];
int P[N], sol[N];

int name(int x) {
    if (x==P[x]) return x;
    P[x]=name(P[x]);
    return P[x];
}

void mrg(int x, int y) {
    x=name(x); y=name(y);
    if (x==y) return;
    P[x]=y;
}

void load() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i=0; i<q; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        queries[i]=mp(a, b);
        v[m/2].pb(i);
        gran[m/2]=mp(1, m-1);
    }
}

void solve() {
    for (int i=2; i<=m; ++i) {
        for (int j=i*2; j<=n; j+=i) {
            dan[m-i+1].pb(mp(i, j));
            //printf("\n");
        }
    }
//    for (int i=1; i<m; ++i) {
//        printf("dan == %d: ", i);
//        for (pii p:dan[i]) printf("<%d, %d> ", p.X, p.Y);
//        printf("\n");
//    }
    while (1) {
        int cnt=0;
        for (int i=1; i<=n; ++i) P[i]=i;
        for (int i=1; i<m; ++i) {
            for (pii pp:dan[i]) mrg(pp.X, pp.Y);
            for (int p:v[i]) {
                int x=queries[p].X, y=queries[p].Y;
                //printf("mid == %d, query: <%d, %d>, lo == %d, hi == %d\n", i, x, y, gran[i].X, gran[i].Y);
                int lo, hi, mid;
                if (name(x)==name(y)) {
                    lo=gran[i].X; hi=i;
                }
                else {
                    lo=i+1; hi=gran[i].Y;
                }
                //printf("novi lo == %d, hi == %d\n", lo, hi);
                //system("pause");
                mid=(lo+hi)/2;
                gran2[mid]=mp(lo, hi);
                if (lo==hi) {
                    sol[p]=lo;
                }
                else {
                    vn[mid].pb(p);
                    ++cnt;
                }
            }
            v[i].clear();
        }
        if (cnt==0) break;
        for (int i=1; i<m; ++i) {
                gran[i]=gran2[i];
            for (int pp:vn[i]) v[i].pb(pp);
            vn[i].clear();
        }
    }
    for (int i=0; i<q; ++i) {
        if (sol[i]==m-1) {
            if (name(queries[i].X)==name(queries[i].Y)) printf("%d\n", m-1);
            else printf("%d\n", m);
        }
        else printf("%d\n", sol[i]);
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

pictionary.cpp: In function 'void load()':
pictionary.cpp:39: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:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

• 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