Submission #399172

#	Time	Username	Problem	Language	Result	Execution time	Memory
399172		Jarif_Rahman	Werewolf (IOI18_werewolf)	C++17	0 / 100	4073 ms	24628 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct dsu{
    int n;
    vector<int> sz, p;
    dsu(int nn){
        n = nn;
        sz.resize(n, 1);
        p.resize(n);
        for(int i = 0; i < n; i++) p[i] = i;
    }
    int get(int x){
        if(p[x] != x) p[x] = get(p[x]);
        return p[x];
    }
    void unite(int a, int b){
        a = get(a), b  = get(b);
        if(a == b) return;
        if(sz[b] > sz[a]) swap(a, b);
        sz[a]+=sz[b];
        sz[b] = 0;
        p[b] = a;
    }
};

vector<int> check_validity(int n, vector<int> U, vector<int> V, vector<int> ss, vector<int> ee, vector<int> L, vector<int> R){
    int m = U.size(), q = ss.size();
    vector<pair<int, int>> edgel(m), edger(m);
    cerr << m << " d\n";
    for(int i = 0; i < m; i++)  edgel[i] = {U[i], V[i]}, edger[i] = {U[i], V[i]};

    sort(edgel.begin(), edgel.end(), [&](pair<int, int> a, pair<int, int> b){
        return max(a.f, a.sc) < max(b.f, b.sc);
    });
    sort(edger.begin(), edger.end(), [&](pair<int, int> a, pair<int, int> b){
        return min(a.f, a.sc) > min(b.f, b.sc);
    });

    vector<int> ans;

    for(int i = 0; i < q; i++){
        cerr << L[i] << " " << R[i] << " " << ss[i] << " " << ee[i] << " d\n";
        dsu ds1(n), ds2(n);
        for(int i = 0; i < m; i++){
            if(max(edgel[i].f, edgel[i].sc) > R[i]) break;
            ds1.unite(edgel[i].f, edgel[i].sc);
        }
        for(int i = 0; i < m; i++){
            if(min(edger[i].f, edger[i].sc) < L[i]) break;
            ds2.unite(edger[i].f, edger[i].sc);
        }
        ans.pb(0);
        for(int j = 0; j < n; j++) if(ds1.get(j) == ds1.get(ee[i]) && ds2.get(j) == ds2.get(ss[i])) ans.back() = 1;
    }
    return ans;
}
/*
6 6 1
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
*/
/*
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: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51