Submission #1049042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049042		n1k	Werewolf (IOI18_werewolf)	C++17	15 / 100	746 ms	524288 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct seg{
	int lb=0, rb=0;
    ll sum=0;
    seg *l=nullptr, *r=nullptr;
	void ext(){
		if(not l and lb!=rb){
			int mb = (lb+rb)/2;
			l = new seg{lb, mb}, r = new seg{mb+1, rb};
		}
	}
	void upd(int x, ll val){
		if(not(lb<=x and x<=rb)) return;
		if(lb==rb){
			sum += val;
		}else{
			ext();
			l->upd(x, val);
			r->upd(x, val);	
			sum = l->sum + r->sum;
		}
	}
	ll qry(int lo, int hi){
		if(hi<lb or rb < lo){
			return 0;
		}
		if(lo <= lb and rb  <= hi){
			return sum;
		}
		ext();
		return l->qry(lo, hi) + r->qry(lo, hi);
	}
};

struct seg2d{
	int lx=0, rx=0, ly=0, ry=0;
	seg tree;
    seg2d *l=nullptr, *r=nullptr;
	void ext(){
		if(not l and lx!=rx){
			int mb = (lx+rx)/2;
			l = new seg2d{lx, mb, ly, ry, seg{ly, ry}}, r = new seg2d{mb+1, rx, ly, ry, seg{ly, ry}};
		}
	}
	void upd(int x, int y, ll val){
		if(not(lx<=x and x<=rx)) return;
		if(lx <= x and x <= rx){
			tree.upd(y, val);
		}
		ext();
		if(l){
			l->upd(x, y, val);
			r->upd(x, y, val);	
		}
	}
	ll qry(int lox, int hix, int loy, int hiy){
		if(hix<lx or rx < lox){
			return 0;
		}
		if(lox <= lx and rx  <= hix){
			return tree.qry(loy, hiy);
		}
		ext();
		return l->qry(lox, hix, loy, hiy) + r->qry(lox, hix, loy, hiy);
	}
};

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    int M = X.size();
    std::vector<int> A(Q);

    auto calc = [&](vector<array<int, 3>> e){
        int t = N;
        vector<vector<int>> g(2*N+5);
        vector<int> p(2*N+5, -1);

        auto find = [&](auto find, int u){
            if(p[u]==-1) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                g[t].push_back(a);
                g[t].push_back(b);
                p[a]=t;
                p[b]=t;
                t++; 
            }
        };
        
        for(auto [cost, u, v]:e){
            join(u, v);
        }
        vector<int> order(N);
        int num = 0; 
        auto dfs = [&](auto dfs, int u) -> void {
            for(int v:g[u]){
                dfs(dfs, v);
            }
            if(u<N)
                order[u]=num++;
        };
        dfs(dfs, t-1);
        return order;
    };

    vector<array<int, 2>> ivx(Q), ivy(Q);

    auto calcinterval = [&](vector<array<int, 3>> e, vector<int> order){
        int t = N;
        vector<int> p(N);
        vector<array<int, 2>> mask(N);
        for(int i=0; i<N; i++) {
            mask[i][0]=mask[i][1]=order[i];
            p[i]=i;
        }

        auto find = [&](auto find, int u){
            if(p[u]==u) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                p[a] = b;
                mask[b][0] = min(mask[b][0], mask[a][0]);
                mask[b][1] = max(mask[b][1], mask[a][1]);
            }
        };

        vector<array<int, 2>> todo;
        for(int i=0; i<Q; i++){
            todo.push_back({L[i], i});
        }
        sort(todo.begin(), todo.end());
        
        for(auto [cost, u, v]:e){
            while(todo.size() and todo.back()[0] > cost){
                auto [l, id]=todo.back();
                todo.pop_back();
                ivx[id] = mask[find(find, S[id])];
            }
            join(u, v);
        }
        while(todo.size()){
            auto [l, id]=todo.back();
            todo.pop_back();
            ivx[id] = mask[find(find, S[id])];
        }
    };

    auto calcinterval2 = [&](vector<array<int, 3>> e, vector<int> order){
        int t = N;
        vector<int> p(N, -1);
        vector<array<int, 2>> mask(N);
        for(int i=0; i<N; i++) {
            mask[i][0]=mask[i][1]=order[i];
            p[i]=i;
        }

        auto find = [&](auto find, int u){
            if(p[u]==u) return u;
            return p[u]=find(find, p[u]); 
        };
        auto join = [&](int u, int v){
            int a = find(find, u), b = find(find, v);
            if(a!=b){
                p[a] = b;
                mask[b][0] = min(mask[b][0], mask[a][0]);
                mask[b][1] = max(mask[b][1], mask[a][1]);
            }
        };

        vector<array<int, 2>> todo;
        for(int i=0; i<Q; i++){
            todo.push_back({R[i], i});
        }
        sort(todo.begin(), todo.end());
        reverse(todo.begin(), todo.end());
        
        for(auto [cost, u, v]:e){
            while(todo.size() and todo.back()[0] < cost){
                auto [r, id]=todo.back();
                todo.pop_back();
                ivy[id] = mask[find(find, E[id])];
            }
            join(u, v);
        }
        while(todo.size()){
            auto [r, id]=todo.back();
            todo.pop_back();
            ivy[id] = mask[find(find, E[id])];
        }
    };

    vector<array<int, 3>> ex, ey;
    for(int i=0; i<M; i++){
        ex.push_back({min(X[i], Y[i]), X[i], Y[i]});
        ey.push_back({max(X[i], Y[i]), X[i], Y[i]});
    }
    sort(ex.begin(), ex.end());
    reverse(ex.begin(), ex.end());
    sort(ey.begin(), ey.end());

    auto x = calc(ex);
    auto y = calc(ey);

    calcinterval(ex, x);
    calcinterval2(ey, y);

    seg2d tree = {0, N-1, 0, N-1, seg{0, N-1}};
    for(int i=0; i<N; i++){
        tree.upd(x[i], y[i], 1);
    }

    for(int i=0; i<Q; i++){
        auto [x1, x2] = ivx[i];
        auto [y1, y2] = ivy[i];

        A[i] = tree.qry(x1, x2, y1, y2) > 0;
    }

    /*
    cout<<endl;
    for(int i=0; i<N; i++) cout << i << " " << x[i] << endl;
    cout<<endl;
    for(int i=0; i<N; i++) cout << i << " " << y[i] << endl;
    cout<<endl;
    for(int i=0; i<Q; i++) cout << ivx[i][0] << " " << ivx[i][1] << endl;
    cout<<endl;
    for(int i=0; i<Q; i++) cout << ivy[i][0] << " " << ivy[i][1] << endl;
    */

    return A;
}

Compilation message (stderr)

werewolf.cpp: In lambda function:
werewolf.cpp:120:13: warning: unused variable 't' [-Wunused-variable]
  120 |         int t = N;
      |             ^
werewolf.cpp: In lambda function:
werewolf.cpp:163:13: warning: unused variable 't' [-Wunused-variable]
  163 |         int t = N;
      |             ^

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