oj.uz

답안 #93542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93542 2019-01-09T12:35:46 Z BartolM Pictionary (COCI18_pictionary) C++17
126 / 140
 454 ms 66560 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+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) {
            while (!vn[i].empty()) {
                v[i].pb(vn[i].back());
                vn[i].pop_back();
            }
        }
    }
    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 8440 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 23664 KB Output is correct
2 Correct 44 ms 18336 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 29872 KB Output is correct
2 Correct 60 ms 25096 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 28232 KB Output is correct
2 Correct 92 ms 26476 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 31672 KB Output is correct
2 Correct 103 ms 24988 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 205 ms 42596 KB Output is correct
2 Correct 182 ms 31596 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 26216 KB Output is correct
2 Correct 284 ms 49144 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 57900 KB Output is correct
2 Correct 454 ms 52788 KB Output is correct

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 435 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -