Submission #1284830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284830		Sir_Ahmed_Imran	Island Hopping (JOI24_island)	C++17	35 / 100	4 ms	560 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 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++){
        G[i].append(i);
        c[i] = i;
        s.append({0, i});
    }
    e = 0;
    for(int k = 1; k < n && e < n - 1; k++){
        for(auto & [p, i] : s){
            j = query(i, k);
            if(c[i] == c[j]){
                if(nei[i][j])
                    t.append({j, i});
            }
            else if(j > p)
                x[{j, c[i]}].append(i);
        }
        for(auto & [i, j] : x){
            if(j.size() == 1 && c[j[0]] != c[i.ff]){
                nei[j[0]][i.ff] = nei[i.ff][j[0]] = 1;
                t.append({i.ff, j[0]});
                join(j[0], i.ff);
                e++;
            }
        }
        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]) 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: 0 / 15
• Subtask 7: 0 / 22
• Subtask 8: 0 / 28