20315번 - 야바위

C++14

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

struct Query{
    int type, ord, op, a, b, id;
    bool operator < (const Query &t) const {
        return tie(ord, type) < tie(t.ord, t.type);
    }
};

set<int> vec[303030];

int k, n, q, ans[303030];
vector<Query> qry;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> k >> n >> q;
    for(int i=1; i<n; i++){
        int op, a, b; cin >> op >> a >> b;
        qry.push_back({1, i, op, a, b, 0});
    }
    for(int i=1; i<=q; i++){
        int s, m, op, a, b; cin >> s >> m >> op >> a >> b;
        qry.push_back({0, m, op, a, b, i});
        vec[s].insert(i);
    }
    sort(all(qry));
    for(auto i : qry){
        int op = i.op, a = i.a, b = i.b;
        if(op == 1){
            if(i.type){
                swap(vec[a], vec[b]);
            }
            else if(vec[a].count(i.id)){
                vec[a].erase(i.id);
                vec[b].insert(i.id);
            }
            else if(vec[b].count(i.id)){
                vec[b].erase(i.id);
                vec[a].insert(i.id);
            }
        }
        else{
            if(i.type){
                if(vec[a].size() > vec[b].size()) swap(vec[a], vec[b]);
                for(auto j : vec[a]) vec[b].insert(j);
                vec[a].clear();
            }
            else if(vec[a].count(i.id)){
                vec[a].erase(i.id);
                vec[b].insert(i.id);
            }
        }
    }
    
    for(int i=1; i<=k; i++){
        for(auto j : vec[i]) ans[j] = i;
    }
    for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}

결과	메모리	시간	코드 길이
180점	64832	824	1740

문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말