제출 #1329074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1329074		Faisal_Saqib	Drzava (COCI15_drzava)	C++20	160 / 160	163 ms	52700 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=5e4+1,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];
        pos[y][j]|=pos[x][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++)
    {
        ll x,y,kt;
        cin>>x>>y>>kt;
        a.push_back({x,y,i});
        par[i]=i;
        pos[i][(ll)(kt)%k]=1;
    }
    sort(begin(a),end(a));
    for(int i=0;i<n;i++)
    {
        for(int p=1;p<=25;p++)
        {
            int j=i+p;
            if(0<=j and j<n)
            {
                edge.push_back({((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1])),a[i][2],a[j][2]});
                // edge.push_back({});
                // cout<<"adding "<<i<<' '<<j<<endl;
            }
        }
    }
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<i;j++)
    //     {
    //         edge.push_back({((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(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;
        }
    }
}

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