oj.uz

Submission #93536

# Submission time Handle Problem Language Result Execution time Memory
93536 2019-01-09T12:26:47 Z BartolM Pictionary (COCI18_pictionary) C++17
126 / 140
 433 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+5;

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);
            for (pip p:v[i]) {
                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;
                }
            }
            v[i].clear();
        }
        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;
}

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8440 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 11424 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 23792 KB Output is correct
2 Correct 45 ms 18408 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 29884 KB Output is correct
2 Correct 62 ms 25124 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 28408 KB Output is correct
2 Correct 102 ms 26640 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 31912 KB Output is correct
2 Correct 107 ms 25296 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 42596 KB Output is correct
2 Correct 166 ms 31828 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 26344 KB Output is correct
2 Correct 297 ms 49300 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 58068 KB Output is correct
2 Correct 432 ms 52968 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 433 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -