제출 #93540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93540		BartolM	Pictionary (COCI18_pictionary)	C++17	126 / 140	485 ms	66560 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+10;

int n, m, q;
pii queries[N];
vector <pip> 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(mp(i, 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);
            while (!v[i].empty()) {
                pip p=v[i].back();
                v[i].pop_back();
                int x=queries[p.X].X, y=queries[p.X].Y;
                //printf("mid == %d, query: <%d, %d>, lo == %d, hi == %d\n", i, x, y, p.Y.X, p.Y.Y);
                int lo, hi, mid;
                if (name(x)==name(y)) {
                    lo=p.Y.X; hi=i;
                }
                else {
                    lo=i+1; hi=p.Y.Y;
                }
                //printf("novi lo == %d, hi == %d\n", lo, hi);
                mid=(lo+hi)/2;
                if (lo==hi) {
                    sol[p.X]=lo;
                }
                else {
                    vn[mid].pb(mp(p.X, mp(lo, hi)));
                    ++cnt;
                }
            }
        }
        if (cnt==0) break;
        for (int i=1; i<m; ++i) {
            for (pip 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;
}

컴파일 시 표준 에러 (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: 0 / 14