【題解】Codeforces EDU Course-2 Lesson-7-2 A. People are leaving

【題目敘述】http://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/A
【解題想法】並查集進階應用,尋找右邊(也可能是左邊)最近的目標

#include <iostream>
using namespace std;
 
int n, m, p[1000005];
 
int pa(int x){
    if (x == p[x]) return x;
    return p[x] = pa(p[x]);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n+1; i++){
        p[i] = i;
    }
    char c;
    for (int i = 0, x; i < m; i++){
        cin >> c >> x;
        if (c == '?'){
            if (pa(x) == n+1) cout << -1 << "\n";
            else cout << pa(x) << "\n";
        }
        else{
            p[x] = pa(x+1);
        }
    }
}

分享本文 Share with friends