제출 #1332546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332546		opeleklanos	송신탑 (IOI22_towers)	C++20	0 / 100	4117 ms	1578952 KiB

towers

#include <set>
#include <vector>
#include <iostream>
using namespace std;

int k = 0;

vector<int> h;
int n;

void init (int n1, vector<int> h1){
    n = n1;
    h = h1;

}

int max_towers(int l, int r, int d){
    vector<set<int>> adj(n, set<int>{});
    for(int i = l; i<r; i++){
        int maxH = h[i+1];
        adj[i].insert(i+1);
        adj[i+1].insert(i);
        for(int j = i+2; j<=r; j++){
            if(h[i] + d > maxH || h[j] + d > maxH){
                adj[i].insert(j);
                adj[j].insert(i);
            }
            maxH = max(maxH, h[j]);
        }
    }

    int ans = 0;
    vector<int> vis(n, 0);
    while(true){
        int minDeg = n+10;
        int m = -1;
        for(int i = 0; i<n; i++){
            if(!vis[i] && adj[i].size()<minDeg){
                m = i;
                minDeg = adj[i].size();
            }
        }
        if(m == -1){
            return ans;
        }
        vis[m] = 1;
        for(auto i : adj[m]){
            vis[i] = 1;
            for(auto j : adj[i]){
                if(j!=m) adj[j].erase(adj[j].find(i));
            }
        }
        ans++;
    }
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23