結果
問題 | No.2923 Mayor's Job |
ユーザー |
![]() |
提出日時 | 2024-10-12 15:05:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 527 ms / 2,000 ms |
コード長 | 1,432 bytes |
コンパイル時間 | 1,264 ms |
コンパイル使用メモリ | 101,864 KB |
最終ジャッジ日時 | 2025-02-24 17:52:18 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include<iostream> #include<vector> #include<cmath> #include<queue> using namespace std; long long f(long long a,long long b,long long c,long long d){ return (a-c)*(a-c)+(b-d)*(b-d); } int main() { long long n,k; cin >> n >> k; k*=k; vector<int>h(n); for(int i=0;i<n;i++)cin >> h[i]; vector<pair<int,int>>num(n); for(int i=0;i<n;i++)cin >> num[i].first >> num[i].second; vector<vector<int>>graph(n); vector<int>amount(n,0); for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(f(num[i].first,num[i].second,num[j].first,num[j].second)<=k){ if(h[i]>h[j]){ graph[j].emplace_back(i+1); amount[i]++; } else if(h[i]<h[j]){ graph[i].emplace_back(j+1); amount[j]++; } } vector<bool>life(n,true); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>prq; for(int i=0;i<n;i++)prq.push(make_pair(amount[i],i+1)); while(prq.size()){ pair<int,int>hako=prq.top(); prq.pop(); int a=hako.second; if(amount[a-1]!=hako.first || life[a-1]==false)continue; bool ok=false; for(int i=0;i<graph[a-1].size();i++)if(life[graph[a-1][i]-1])ok=true; if(ok==false)continue; for(int i=0;i<graph[a-1].size();i++)if(life[graph[a-1][i]-1]){ amount[graph[a-1][i]-1]--; prq.push(make_pair(amount[graph[a-1][i]-1],graph[a-1][i])); } life[a-1]=false; } int cnt=0; for(int i=0;i<n;i++)if(life[i])cnt++; cout << cnt << endl; }