제출 #1142444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142444		dombly	Werewolf (IOI18_werewolf)	C++20	15 / 100	4091 ms	13684 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
#define F first
#define S second
#define pb push_back

using namespace std;

struct DSU {
    vector<int>par;
    void init(int n) {
        par.resize(n + 10);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        return (x == par[x] ? x : par[x] = get(par[x]));
    }
    void unite(int u,int v) {
        u = get(u); v = get(v);
        if(u != v) par[u] = v;
    }
    bool same(int u,int v) {
        return (get(u) == get(v));
    }
};

bool cmpL(pair<int,int>a,pair<int,int>b) {
    return min(a.F,a.S) > min(b.F,b.S);
}

bool cmpR(pair<int,int>a,pair<int,int>b) {
    return max(a.F,a.S) < max(b.F,b.S);
}

vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
    vector<pair<int,int>>edges;
    int m = X.size(),q = S.size(),n = N;
    for(int i = 0; i < m; i++) {
        edges.pb({X[i],Y[i]});
    }
    vector<int>ans(q);
    for(int j = 0; j < q; j++) {
        int s = S[j],e = E[j],l = L[j],r = R[j];
        DSU dsu[2];
        dsu[0].init(n);
        dsu[1].init(n);
        sort(edges.begin(),edges.end(),cmpL);
        for(int i = 0; i < m; i++) {
            if(min(edges[i].F,edges[i].S) < l) break;
            dsu[0].unite(edges[i].F,edges[i].S);
        }
        sort(edges.begin(),edges.end(),cmpR);
        for(int i = 0; i < m; i++) {
            if(max(edges[i].F,edges[i].S) > r) break;
            dsu[1].unite(edges[i].F,edges[i].S);
        }
        for(int i = 0; i < n; i++) {
            if(dsu[0].same(i,s) && dsu[1].same(i,e)) ans[j] = 1;
        }
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51