제출 #1329038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1329038		Faisal_Saqib	Drzava (COCI15_drzava)	C++20	8 / 160	129 ms	131072 KiB

drzava

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
int n,k;
bool win=0;
const int N=1e5,K=31;
bool pos[N][K];
int par[N];
bool np[K];
int get(int x)
{
    return (par[x]==x)?x:par[x]=get(par[x]);
}
void merge(int x,int y)
{
    x=get(x);
    y=get(y);
    if(x==y)return;
    par[x]=y;
    for(int i=0;i<k;i++)
    {
        for(int j=0;j<k;j++)
        {
            np[(i+j)%k]|=(pos[x][i]&pos[y][j]);
        }
    }
    for(int j=0;j<k;j++)
    {
        pos[y][j]=np[j];
        np[j]=0;
    }
    win|=(pos[y][0]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    vector<array<ll,3>> a,edge;
    for(int i=0;i<n;i++)
    {
        int x,y,kt;
        cin>>x>>y>>kt;
        a.push_back({x,y,kt});
        par[i]=i;
        pos[i][kt%k]=1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            edge.push_back({1ll*((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+1ll*(a[i][1]-a[j][1])*(a[i][1]-a[j][1])),i,j});
        }
    }
    sort(begin(edge),end(edge));
    for(auto cur:edge)
    {
        merge(cur[1],cur[2]);
        // {
            if(win)
            {
                ld sq=sqrtl(cur[0]);
                cout<<fixed<<setprecision(3)<<round(sq*1000)/1000<<endl;
                return 0;
            }
        // }
    }
    // sort(begin(a),end(a));
    // for(auto x:a)
    // {
    //     cout<<x[0]<<' '<<x[1]<<' '<<x[2]<<endl;
    // }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 8
• Subtask 5: 0 / 8
• Subtask 6: 0 / 8
• Subtask 7: 8 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8
• Subtask 13: 0 / 8
• Subtask 14: 0 / 8
• Subtask 15: 0 / 8
• Subtask 16: 0 / 8
• Subtask 17: 0 / 8
• Subtask 18: 0 / 8
• Subtask 19: 0 / 8
• Subtask 20: 0 / 8