oj.uz

Submission #47731

# Submission time Handle Problem Language Result Execution time Memory
47731 2018-05-06T23:36:50 Z IvanC Drzava (COCI15_drzava) C++17
160 / 160
 182 ms 19296 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef tuple<int,int,int> trinca;
const int MAXN = 50010;
const int MAXK = 32;
int pai[MAXN],possivel[MAXN][MAXK],X[MAXN],Y[MAXN],Z[MAXN],N,K;
vector<trinca> ordenado;

int find(int x){
    if(x == pai[x]) return x;
    return pai[x] = find(pai[x]);
}

void join(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(x > y) swap(x,y);
    int novo[MAXK];
    for(int i = 0;i<K;i++) novo[i] = possivel[x][i] | possivel[y][i];
    for(int i = 0;i<K;i++){
        for(int j = 0;j<K;j++){
            novo[(i+j) % K] |= (possivel[x][i] & possivel[y][j]);
        }
    }
    for(int i = 0;i<K;i++) possivel[x][i] |= novo[i];
    pai[y] = x;
}

inline ll dist(int a,int b){
    return 1LL*(X[a] - X[b])*(X[a] - X[b]) + 1LL*(Y[a] - Y[b])*(Y[a] - Y[b]);
}

int checa(ll maximo){
    int teto = (int)ceil(sqrt(maximo)) + 3;
    for(int i = 1;i<=N;i++){
        pai[i] = i;
        for(int j = 0;j<K;j++){
            possivel[i][j] = 0;
        }
        possivel[i][Z[i]] = 1;
    }
    set<ii> caixa;
    int ponteiro = 1;
    caixa.insert(ii(Y[1],1));
    for(int i = 2;i<=N;i++){
        while(X[i] - X[ponteiro] > teto){
            caixa.erase(ii(Y[ponteiro],ponteiro));
            ponteiro++;
        }
        for(set<ii>::iterator it = caixa.lower_bound(ii(Y[i] - teto,-1));it != caixa.end();it++){
            int j = (*it).second;
            if(abs(Y[j] - Y[i]) > teto) break;
            if(dist(i,j) <= maximo) join(i,j);
            if(possivel[find(i)][0]) return 1;
        }
        if(possivel[find(i)][0]) return 1;
        caixa.insert(ii(Y[i],i));
    }
    return 0;
}

int main(){
    scanf("%d %d",&N,&K);
    for(int i = 0;i<N;i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        ordenado.push_back(make_tuple(x,y,z));
    }
    sort(ordenado.begin(),ordenado.end());
    for(int i = 1;i<=N;i++){
        X[i] = get<0>(ordenado[i-1]);
        Y[i] = get<1>(ordenado[i-1]);
        Z[i] = get<2>(ordenado[i-1]) % K;
    }
    ll ini = 0, fim = 2*1e18,meio,ans = 2*1e18;
    while(ini <= fim){
        meio = ini + (fim - ini)/2;
        if(checa(meio)){
            ans = meio;
            fim = meio - 1;
        }
        else{
            ini = meio + 1;
        }
    }
    printf("%.3lf\n",sqrt(ans));
    return 0;
}

Compilation message

drzava.cpp: In function 'int main()':
drzava.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&K);
     ~~~~~^~~~~~~~~~~~~~~
drzava.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 2 ms 440 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 444 KB Output is correct
2 Correct 4 ms 576 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 576 KB Output is correct
2 Correct 4 ms 724 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 5 ms 724 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 4 ms 820 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 832 KB Output is correct
2 Correct 4 ms 944 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 944 KB Output is correct
2 Correct 4 ms 1012 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 38 ms 5000 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 149 ms 9988 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9988 KB Output is correct
2 Correct 182 ms 10964 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10964 KB Output is correct
2 Correct 116 ms 11648 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11648 KB Output is correct
2 Correct 119 ms 13176 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13176 KB Output is correct
2 Correct 106 ms 14156 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14156 KB Output is correct
2 Correct 122 ms 15040 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15040 KB Output is correct
2 Correct 118 ms 15944 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15944 KB Output is correct
2 Correct 121 ms 16736 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16736 KB Output is correct
2 Correct 122 ms 17608 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17608 KB Output is correct
2 Correct 100 ms 18436 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18436 KB Output is correct
2 Correct 103 ms 19296 KB Output is correct