Submission #74772411

---

Source Code Expand

#include<iostream>
using namespace std;
const int N=2e5+10;
#include<queue>

struct participant
{
    int p, pair, num;
    priority_queue<int, vector<int>, greater<int> > v;
    participant()
        :pair(0) {}
} a[N];
auto cmp=[](const participant& a, const participant& b){ return a.p<b.p; };
priority_queue<participant, vector<participant>, decltype(cmp)> q(cmp);
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; ++i)
        cin>>a[i].p, a[i].num=i, q.emplace(a[i]);
    int u, v;
    while (m--)
    {
        cin>>u>>v;
        a[u].v.emplace(v), a[v].v.emplace(u);
    }
    while(!q.empty()){
        auto t=q.top().num;
        if(!a[t].pair){
            int c=a[t].v.top();
            while(!a[t].v.empty()){
                c=a[t].v.top();
                if(!a[c].pair){
                    a[t].pair=c, a[c].pair=t;
                    break;
                }
                a[t].v.pop();
            }
        }
        q.pop();
    }
    cout<<a[1].pair;
    return 0;
}

Submission Info

Judge Result