제출 #1284847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284847		Sir_Ahmed_Imran	Island Hopping (JOI24_island)	C++17	72 / 100	2065 ms	532 KiB

island

#include "island.h"
#include <bits/stdc++.h>
using namespace std;

#define MAXN 301
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int k[MAXN];
int c[MAXN];
vector<int> G[MAXN];
bool nei[MAXN][MAXN];

void join(int i, int j){
    int k = c[j];
    for(auto & v : G[k]){
        G[c[i]].append(v);
        c[v] = c[i];
    }
    G[k].clear();
}

void solve(int n, int l){
    int j, e;
    vector<pii> s, t;
    map<pii, vector<int>> x;
    for(int i = 1; i <= n; i++){
        s.append({0, i});
        G[i].append(i);
        c[i] = i;
        k[i] = 1;
    }
    e = 0;
    for(int it = 1; e < n - 1; it++){
        for(auto & [p, i] : s){
            if(l < 3 * n && k[i] > 2)
                continue;
            j = query(i, k[i]);
            k[i]++;
            if(j < p) continue;
            if(nei[j][i]){
                if(c[i] != c[j]){
                    nei[i][j] = 1;
                    t.append({j, i});
                    t.append({i, j});
                    join(i, j);
                    e++;
                }
            }
            else nei[i][j] = 1;
        }
        swap(s, t);
        t.clear();
        x.clear();
    }
    for(int i = 1; i < n; i++)
        for(int j = i + 1; j <= n; j++)
            if(nei[i][j] && nei[j][i]) 
                answer(i, j);
}

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