oj.uz

답안 #93554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93554 2019-01-09T14:39:34 Z BartolM Pictionary (COCI18_pictionary) C++17
140 / 140
 447 ms 39388 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7800 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8952 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 13672 KB Output is correct
2 Correct 37 ms 11760 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 16036 KB Output is correct
2 Correct 52 ms 14340 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 17120 KB Output is correct
2 Correct 87 ms 16088 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 18896 KB Output is correct
2 Correct 94 ms 15752 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 24376 KB Output is correct
2 Correct 173 ms 20188 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 16752 KB Output is correct
2 Correct 314 ms 28612 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 32848 KB Output is correct
2 Correct 392 ms 30572 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 428 ms 39388 KB Output is correct
2 Correct 447 ms 34416 KB Output is correct