제출 #1284977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284977		Muhammad_Aneeq	Island Hopping (JOI24_island)	C++20	65 / 100	7 ms	844 KiB

island

#include "island.h"
#include "iostream"
#include "bits/stdc++.h"
using namespace std;
int const MAXN=310;
int vis[MAXN]={};
int val[MAXN][MAXN]={};
bool nei[MAXN][MAXN]={};
int deg[MAXN]={};
int par[MAXN]={};
int ask(int i,int j)
{
    if (val[i][j]==0)
        val[i][j]=query(i,j);
    return val[i][j];
}
int root(int n)
{
    return (par[n]==n?n:par[n]=root(par[n]));
}
void merge(int u,int v)
{
    u=root(u);
    v=root(v);
    par[v]=u;
}
void solve(int N, int L) 
{
    for (int i=1;i<=N;i++)
        par[i]=i;
    int cnt=0;
    for (int i=1;i<=N;i++)
    {
        int j=deg[i]+1;
        while (j<N&&cnt<N-1)
        {
            int z=ask(i,j);
            if (i==1&&j==1)
            {
                val[z][1]=1;
            }
            if (z<i)
            {
                break;
            }
            if (root(i)==root(z))
            { 
                j++;
                break;
            }
            if (ask(z,deg[z]+1)==i)
            {
                cnt++;
                nei[i][z]=1;
                merge(i,z);
                deg[i]++;
                deg[z]++;
            }
            else
                break;
            j++;
        }
    }
    set<pair<int,int>>ed;
    for (int i=1;i<=N;i++)
    {
        for (int j=i+1;j<=N;j++)
            if (nei[i][j])
                ed.insert({i,j});
    }
    for (auto [i,j]:ed)
    {
        // cout<<i<<' '<<j<<endl;
        answer(i,j);
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 9 / 9
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 22 / 22
• Subtask 8: 0 / 28