oj.uz

Submission #93546

# Submission time Handle Problem Language Result Execution time Memory
93546 2019-01-09T12:56:48 Z patrikpavic2 Pictionary (COCI18_pictionary) C++17
126 / 140
 801 ms 46908 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 = 1e6 + 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 796 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 4844 KB Output is correct
2 Correct 127 ms 4800 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 5836 KB Output is correct
2 Correct 179 ms 5428 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 8788 KB Output is correct
2 Correct 177 ms 8604 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 13024 KB Output is correct
2 Correct 251 ms 12636 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 17488 KB Output is correct
2 Correct 323 ms 16464 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 14800 KB Output is correct
2 Correct 542 ms 26576 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 28392 KB Output is correct
2 Correct 607 ms 31008 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 46908 KB Output is correct
2 Incorrect 801 ms 34480 KB Output isn't correct