oj.uz

Submission #1049347

# Submission time Handle Problem Language Result Execution time Memory
1049347 2024-08-08T16:51:44 Z n1k Werewolf (IOI18_werewolf) C++17
100 / 100
 779 ms 106536 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct seg{
	int lb=0, rb=0;
	vector<int> v;
    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 build(vector<vector<int>> &vv){
		if(lb==rb){
			v = vv[lb];
		}else{
			ext();
			l->build(vv);
			r->build(vv);	
			merge(l->v.begin(), l->v.end(), r->v.begin(), r->v.end(), back_inserter(v));
		}
	}
	ll qry(int lox, int hix, int loy, int hiy){
		if(hix<lb or rb < lox){
			return 0;
		}
		if(lox <= lb and rb  <= hix){
			int ll = lower_bound(v.begin(), v.end(), loy) - v.begin();
			int rr = lower_bound(v.begin(), v.end(), hiy + 1) - v.begin() - 1;
			return max(0, rr - ll + 1);
		}
		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);


    seg tree = {0, N-1};
    vector<vector<int>> vv(N);
    for(int i=0; i<N; i++){
        vv[x[i]].push_back(y[i]);
    }
    tree.build(vv);

    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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 1740 KB Output is correct
11 Correct 5 ms 1740 KB Output is correct
12 Correct 4 ms 1736 KB Output is correct
13 Correct 5 ms 1752 KB Output is correct
14 Correct 4 ms 1736 KB Output is correct
15 Correct 5 ms 1900 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 92316 KB Output is correct
2 Correct 485 ms 97512 KB Output is correct
3 Correct 505 ms 93568 KB Output is correct
4 Correct 436 ms 93140 KB Output is correct
5 Correct 464 ms 92536 KB Output is correct
6 Correct 384 ms 92736 KB Output is correct
7 Correct 352 ms 92528 KB Output is correct
8 Correct 495 ms 97348 KB Output is correct
9 Correct 342 ms 93800 KB Output is correct
10 Correct 371 ms 92676 KB Output is correct
11 Correct 378 ms 92524 KB Output is correct
12 Correct 319 ms 92740 KB Output is correct
13 Correct 468 ms 97092 KB Output is correct
14 Correct 463 ms 96576 KB Output is correct
15 Correct 520 ms 97028 KB Output is correct
16 Correct 462 ms 96836 KB Output is correct
17 Correct 367 ms 92532 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8 ms 1740 KB Output is correct
11 Correct 5 ms 1740 KB Output is correct
12 Correct 4 ms 1736 KB Output is correct
13 Correct 5 ms 1752 KB Output is correct
14 Correct 4 ms 1736 KB Output is correct
15 Correct 5 ms 1900 KB Output is correct
16 Correct 388 ms 92316 KB Output is correct
17 Correct 485 ms 97512 KB Output is correct
18 Correct 505 ms 93568 KB Output is correct
19 Correct 436 ms 93140 KB Output is correct
20 Correct 464 ms 92536 KB Output is correct
21 Correct 384 ms 92736 KB Output is correct
22 Correct 352 ms 92528 KB Output is correct
23 Correct 495 ms 97348 KB Output is correct
24 Correct 342 ms 93800 KB Output is correct
25 Correct 371 ms 92676 KB Output is correct
26 Correct 378 ms 92524 KB Output is correct
27 Correct 319 ms 92740 KB Output is correct
28 Correct 468 ms 97092 KB Output is correct
29 Correct 463 ms 96576 KB Output is correct
30 Correct 520 ms 97028 KB Output is correct
31 Correct 462 ms 96836 KB Output is correct
32 Correct 367 ms 92532 KB Output is correct
33 Correct 531 ms 94272 KB Output is correct
34 Correct 282 ms 48544 KB Output is correct
35 Correct 714 ms 97064 KB Output is correct
36 Correct 482 ms 93680 KB Output is correct
37 Correct 637 ms 96080 KB Output is correct
38 Correct 569 ms 94160 KB Output is correct
39 Correct 398 ms 101112 KB Output is correct
40 Correct 500 ms 106536 KB Output is correct
41 Correct 522 ms 95752 KB Output is correct
42 Correct 446 ms 93104 KB Output is correct
43 Correct 779 ms 104496 KB Output is correct
44 Correct 611 ms 96084 KB Output is correct
45 Correct 581 ms 101836 KB Output is correct
46 Correct 765 ms 100916 KB Output is correct
47 Correct 475 ms 97284 KB Output is correct
48 Correct 510 ms 97188 KB Output is correct
49 Correct 522 ms 96996 KB Output is correct
50 Correct 530 ms 96628 KB Output is correct
51 Correct 509 ms 106284 KB Output is correct
52 Correct 470 ms 105468 KB Output is correct