Submission #139372

#	Time	Username	Problem	Language	Result	Execution time	Memory
139372		atoiz	Werewolf (IOI18_werewolf)	C++14	100 / 100	3739 ms	248784 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <unordered_set>
#include <cstring>
#include <stack>

using namespace std;

struct DSU
{
    vector<int> a;

    DSU(int n)
    {
    	a.resize(n);
    	for (int i = 0; i < n; ++i) a[i] = i;
    }

    int root(int x)
    {
        return (x == a[x] ? x : a[x] = root(a[x]));
    }

    void merge(int x, int y) // root[y] = x
    {
        a[root(y)] = root(x);
    }

    bool same(int x, int y)
    {
        return root(x) == root(y);
    }
};

struct IT
{
	int n;
    vector< unordered_set<int> > a;

    IT(int _n)
    {
		n = _n;
        a.resize(4*n);
    }

    void update(int x, int from, int to, int root, int s0, int e1, bool add)
    {
        if (to < s0 || e1 < from) return;
        if (from <= s0 && e1 <= to) {
            if (add) a[root].insert(x);
            else a[root].erase( a[root].find(x) );
            return;
        }

        int m = (s0 + e1) / 2;
        update(x, from, to, 2 * root, s0, m, add);
        update(x, from, to, 2 * root + 1, m+1, e1, add);
    }

    void addX(int x, int from, int to)
    {
        update(x, from, to, 1, 0, n-1, 1);
    }

    void removeX(int x, int from, int to)
    {
        update(x, from, to, 1, 0, n-1, 0);
    }

    void get(int pos, int root, int s0, int e1, vector<int>& ans)
    {
        for (int i : a[root]) ans.push_back(i);
        if (s0 == e1) return;
        int m = (s0 + e1) / 2;
        if (pos <= m) get(pos, root * 2, s0, m, ans);
        else get(pos, root * 2 + 1, m+1, e1, ans);
    }

    void get(int pos, vector<int>& ans)
    {
        get(pos, 1, 0, n-1, ans);
    }
};

void dfsTour(int u, vector< vector<int> > &graph, vector<int>& s, vector<int> &e, int &cur)
{
    s[u] = ++cur;
//    cerr << u << endl;
    for (int v : graph[u]) dfsTour(v, graph, s, e, cur);
    e[u] = cur;
}

void dfsEverything(int u, vector< vector<int> > &tree1, vector< vector<int> > &queries, vector<int> &S, vector<int> &startS, vector<int>& endS, vector<int> &ans, IT &it)
{
	// add queries
    for (int qi : queries[u]) {
        it.addX(qi, startS[S[qi]], endS[S[qi]]);
    }

    // process queries
    vector<int> finishedQueries;
    it.get(startS[u], finishedQueries);
    for (int qi : finishedQueries) {
        ans[qi] = 1;
        it.removeX(qi, startS[S[qi]], endS[S[qi]]);
    }

    // process children
    for (int v : tree1[u]) dfsEverything(v, tree1, queries, S, startS, endS, ans, it);

    // remove queries
    for (int qi : queries[u]) {
        if (ans[qi] == 1) continue;
        it.removeX(qi, startS[S[qi]], endS[S[qi]]);
        ans[qi] == 0; // should be redundant
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
	int logN = log2(N) + 1;
	vector<int> ans(S.size(), 0);

	// Convert X & Y -> adjList
	vector< vector<int> > graph(N); // bidirectional
    for (int i = 0; i < X.size(); ++i) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

	// Create tree 1 (<= x)
    vector< vector<int> > tree1(N);
    DSU dsu1(N);
    for (int u = 0; u < N; ++u) {
        for (int v : graph[u]) {
            if (v > u) continue;
            if (dsu1.same(u, v)) continue;
            tree1[u].push_back(dsu1.root(v));
//            cerr << u << " -> " << dsu1.root(v) << endl;
            dsu1.merge(u, v); // order matters!
        }
    }

    // Create par1
    vector< vector<int> > par1(logN + 1, vector<int>(N));
    for (int u = 0; u < N; ++u) {
        for (int v : tree1[u]) {
            par1[0][v] = u;
        }
    }
    par1[0][N-1] = -1;

//    for (int i = 0; i < N; ++i) cerr << par1[0][i] << ' '; cerr << endl;

    for (int i = 1; i <= logN; ++i) {
        for (int u = 0; u < N; ++u) {
			int v = par1[i-1][u];
			par1[i][u] = (v == -1) ? -1 : par1[i-1][v];
        }
    }


	// Create tree 2 (>= x)
    vector< vector<int> > tree2(N);
    DSU dsu2(N);
    for (int u = N-1; u >= 0; --u) {
        for (int v : graph[u]) {
            if (v < u) continue;
            if (dsu2.same(u, v)) continue;
            tree2[u].push_back(dsu2.root(v));
            dsu2.merge(u, v); // order matters!
        }
    }

    // Create par2
    vector< vector<int> > par2(logN + 1, vector<int>(N));
    for (int u = 0; u < N; ++u) {
        for (int v : tree2[u]) {
            par2[0][v] = u;
        }
    }
    par2[0][0] = -1;

//    for (int i = 0; i < N; ++i) cerr << par2[0][i] << ' '; cerr << endl;

    for (int i = 1; i <= logN; ++i) {
        for (int u = 0; u < N; ++u) {
			int v = par2[i-1][u];
			par2[i][u] = (v == -1) ? -1 : par2[i-1][v];
        }
    }

    // Re-write queries
    vector< vector<int> > queries(N);
    for (int qi = 0; qi < S.size(); ++qi) {
		// S[i] <- L[i], tree2
        for (int lg = logN; lg >= 0; --lg) {
            int u = par2[lg][S[qi]];
            if (u >= 0 && u >= L[qi]) S[qi] = u;
        }

		// E[i] <- R[i], tree1
        for (int lg = logN; lg >= 0; --lg) {
            int u = par1[lg][E[qi]];
            if (u >= 0 && u <= R[qi]) E[qi] = u;
        }

//        cerr << S[qi] << ' ' << E[qi] << endl;

        queries[E[qi]].push_back(qi);
    }

	// Check with trees
	// Tree 1: dfs
	// Tree 2: Euler tour + IT

	// Euler tour for tree2
	int cur = -1;
	vector<int> startS(S.size()), endS(S.size());
//	cerr << endl;
	dfsTour(0, tree2, startS, endS, cur);
//	cerr << startS[5] << ' ' << endS[5] << endl;

	// IT for tree2
    IT intervalTree(N);

    // dfs for tree1
    dfsEverything(N-1, tree1, queries, S, startS, endS, ans, intervalTree);

	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfsEverything(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, IT&)':
werewolf.cpp:120:17: warning: value computed is not used [-Wunused-value]
         ans[qi] == 0; // should be redundant
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:131:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); ++i) {
                     ~~^~~~~~~~~~
werewolf.cpp:200:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int qi = 0; qi < S.size(); ++qi) {
                      ~~~^~~~~~~~~~

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