oj.uz

Submission #93547

# Submission time Handle Problem Language Result Execution time Memory
93547 2019-01-09T12:57:18 Z patrikpavic2 Pictionary (COCI18_pictionary) C++17
140 / 140
 814 ms 47420 KB 
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <queue>

#define PB push_back
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int, int> pii;
typedef pair < ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vl;
typedef pair < pii, pii > edg;

const int N = 5e5 + 500;
const int M = 2e6 + 500;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int LOG = 20;
const int OFF = (1 << LOG);
const double EPS = 1e-9;
const double PI = 3.1415926535;

int lo[N], hi[N], koji[N], pr[N], a[M], b[M], c[M], a2[N], b2[N], n, q, m;
vector < edg > v;

int par(int x){
    if(x == pr[x]) return x;
    return pr[x] = par(pr[x]);
}

void mrg(int x,int y){
    x = par(x), y = par(y);
    pr[x] = y;
}

void iterrate(){
    for(int i = 1;i<=n;i++) pr[i] = i;
    vector < edg > qq;

    for(int i = 1;i<=q;i++){
        if(lo[i] == hi[i]) continue;
        qq.PB({{(lo[i] + hi[i] + 1) / 2, i}, {a2[i], b2[i]}});
    }
    sort(qq.begin(), qq.end());
    int j = 0;
    for(int i = 0;i<v.size();i++){
        while(j < qq.size() && v[i].X.X > qq[j].X.X){
            if(par(qq[j].Y.X) != par(qq[j].Y.Y)){
                lo[qq[j].X.Y] = qq[j].X.X;
            }
            else{
                hi[qq[j].X.Y] = qq[j].X.X - 1;
            }
            j++;
        }
        mrg(v[i].Y.X, v[i].Y.Y);
    }
   while(j < qq.size()){
        if(par(qq[j].Y.X) != par(qq[j].Y.Y)){
            lo[qq[j].X.Y] = qq[j].X.X;
        }
        else{
            hi[qq[j].X.Y] = qq[j].X.X - 1;
        }
        j++;
    }
}

int main(){
    scanf("%d%d%d",&n,&m, &q);
    for(int i = 1;i<=q;i++){
        scanf("%d%d", a2 + i, b2 + i);
        lo[i] = 0, hi[i] = N;
    }
    int cr = 0;
    for(int i = 1;i<=m;i++){
        for(int j = 2 * i;j <= n;j += i){
            a[cr] = i;b[cr] = j;c[cr] = m - i + 1;
            cr++;
        }
    }
    m = cr;
    for(int i = 0;i<m;i++){
        v.PB({{c[i], INF}, {a[i], b[i]}});
    }
    sort(v.begin(), v.end());
    for(int i = 0;i<20;i++) iterrate();
    ll sol = 0;
    for(int i = 1;i<=q;i++){
        printf("%d\n", lo[i] + 1);
    }
    return 0;
}

Compilation message

pictionary.cpp: In function 'void iterrate()':
pictionary.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<v.size();i++){
                   ~^~~~~~~~~
pictionary.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < qq.size() && v[i].X.X > qq[j].X.X){
               ~~^~~~~~~~~~~
pictionary.cpp:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j < qq.size()){
          ~~^~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:101:8: warning: unused variable 'sol' [-Wunused-variable]
     ll sol = 0;
        ^~~
pictionary.cpp:83: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:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a2 + i, b2 + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1564 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4816 KB Output is correct
2 Correct 130 ms 4840 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 5800 KB Output is correct
2 Correct 168 ms 5432 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 8760 KB Output is correct
2 Correct 174 ms 8584 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 13020 KB Output is correct
2 Correct 247 ms 12636 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 17444 KB Output is correct
2 Correct 299 ms 16592 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 14672 KB Output is correct
2 Correct 549 ms 26576 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 28360 KB Output is correct
2 Correct 724 ms 30928 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 47420 KB Output is correct
2 Correct 754 ms 35160 KB Output is correct