oj.uz

Submission #417723

# Submission time Handle Problem Language Result Execution time Memory
417723 2021-06-04T08:06:55 Z 2fat2code Werewolf (IOI18_werewolf) C++17
100 / 100
 1181 ms 104336 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)

const int nmax = 200005;

int Q, m, n, par[nmax], perm1[nmax], perm2[nmax], overlap[nmax], pos[nmax], aib[2*nmax], first1[nmax], last1[nmax], first2[nmax], last2[nmax];
vector<int>nod[nmax], nod1[nmax];
vector<int>euler1, euler2;
vector<pair<int,int>>Query[nmax];

struct item{
    int coeff, indx, where;
};

vector<item>Query2[2*nmax];

void update(int pos, int val){
    for(int i=pos;i<=2*n;i+=i&-i){
        aib[i] += val;
    }
}

int qry(int pos){
    if(pos == 0) return 0;
    int rs = 0;
    for(int i=pos;i>=1;i-=i&-i){
        rs += aib[i];
    }
    return rs;
}

int findpar(int x){
    if(par[x] != x){
        par[x] = findpar(par[x]);
    }
    return par[x];
}

void dfs(int s, vector<int>&euler, set<pair<int,int>>&st, int caz, int pr = 0){
    euler.push_back(s);
    for(auto it : nod1[s]){
        dfs(it, euler, st, caz, s);
    }
    for(auto it : Query[s]){
        st.insert({it.sc, it.fr});
    }
    if(caz == 1){
        auto it = st.end();
        while(it != st.begin()){
            --it;
            if(pr == 0){
                perm1[it->sc] = s;
            }
            else{
                if(it->fr > pr){
                    perm1[it->sc] = s;
                    auto it1 = it;
                    it++;
                    st.erase(it1);
                }
                else{
                    break;
                }
            }
        }
    }
    else{
       auto it = st.begin();
       while(it != st.end()){
            if(pr == 0){
                perm2[it->sc] = s;
                ++it;
            }
            else{
                if(it->fr < pr){
                    perm2[it->sc] = s;
                    auto it1 = it;
                    it++;
                    st.erase(it1);
                }
                else{
                    break;
                }
            }
       }
    }
    euler.push_back(s);
}

void construct1(int caz, vector<int>&euler){
    for(int i=1;i<=n;i++) par[i] = i;
    if(caz == 1){
        for(int i=n;i>=1;i--){
            for(auto it : nod[i]){
                if(it > i){
                    int curr = findpar(it);
                    if(curr != i){
                        nod1[i].push_back(curr);
                        par[curr] = i;
                    }
                }
            }
        }
    }
    else{
        for(int i=1;i<=n;i++){
            for(auto it : nod[i]){
                if(it < i){
                    int curr = findpar(it);
                    if(curr != i){
                        nod1[i].push_back(curr);
                        par[curr] = i;
                    }
                }
            }
        }
    }
    if(caz == 1){
        set<pair<int,int>>s;
        dfs(1, euler, s, 1);
    }
    else{
        set<pair<int,int>>s;
        dfs(n, euler, s, 2);
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    Q = S.size();
    n = N;
    m = X.size();
    vector<int> A(Q);
    for(int i=0;i<m;i++) X[i]++, Y[i]++;
    for(int i=0;i<Q;i++) S[i]++, E[i]++, L[i]++, R[i]++;
    for(int i=0;i<m;i++){
        nod[X[i]].push_back(Y[i]);
        nod[Y[i]].push_back(X[i]);
    }
    for(int i=0;i<Q;i++){
        Query[S[i]].push_back({i, L[i]});
    }
    construct1(1, euler1);
    for(int i=0;i<=n;i++){
        nod1[i].clear();
    }
    for(int i=1;i<=n;i++){
        Query[i].clear();
    }
    for(int i=0;i<Q;i++){
        Query[E[i]].push_back({i, R[i]});
    }
    construct1(2, euler2);
    for(int i=0;i<(int)euler1.size();i++){
        if(first1[euler1[i]] == 0) first1[euler1[i]] = (i + 1);
        else{
            last1[euler1[i]] = (i + 1);
        }
    }
    for(int i=0;i<(int)euler2.size();i++){
        if(first2[euler2[i]] == 0) first2[euler2[i]] = (i + 1);
        else{
            last2[euler2[i]] = (i + 1);
        }
    }
    for(int i=0;i<Q;i++){
        Query2[first1[perm1[i]] - 1].push_back({1, i, first2[perm2[i]]});
        Query2[first1[perm1[i]] - 1].push_back({-1, i, last2[perm2[i]]});
        Query2[last1[perm1[i]]].push_back({1, i, last2[perm2[i]]});
        Query2[last1[perm1[i]]].push_back({-1, i, first2[perm2[i]]});
    }
    for(int i=0;i<(int)euler1.size();i++){
        update(first2[euler1[i]], 1);
        update(last2[euler1[i]], 1);
        for(auto it : Query2[i+1]){
            overlap[it.indx] += it.coeff * qry(it.where);
        }
    }
    for(int i=0;i<Q;i++){
        if(overlap[i]){
            A[i] = 1;
        }
    }
    return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 17 ms 23756 KB Output is correct
3 Correct 18 ms 23844 KB Output is correct
4 Correct 17 ms 23804 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 18 ms 23912 KB Output is correct
8 Correct 19 ms 23884 KB Output is correct
9 Correct 17 ms 23792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 17 ms 23756 KB Output is correct
3 Correct 18 ms 23844 KB Output is correct
4 Correct 17 ms 23804 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 18 ms 23912 KB Output is correct
8 Correct 19 ms 23884 KB Output is correct
9 Correct 17 ms 23792 KB Output is correct
10 Correct 28 ms 24740 KB Output is correct
11 Correct 26 ms 24804 KB Output is correct
12 Correct 23 ms 24644 KB Output is correct
13 Correct 24 ms 25044 KB Output is correct
14 Correct 22 ms 24988 KB Output is correct
15 Correct 25 ms 24860 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 84956 KB Output is correct
2 Correct 1162 ms 92300 KB Output is correct
3 Correct 1063 ms 87248 KB Output is correct
4 Correct 1031 ms 84004 KB Output is correct
5 Correct 994 ms 84296 KB Output is correct
6 Correct 910 ms 85356 KB Output is correct
7 Correct 934 ms 84020 KB Output is correct
8 Correct 773 ms 88668 KB Output is correct
9 Correct 685 ms 83848 KB Output is correct
10 Correct 751 ms 86704 KB Output is correct
11 Correct 701 ms 80052 KB Output is correct
12 Correct 737 ms 79188 KB Output is correct
13 Correct 946 ms 94256 KB Output is correct
14 Correct 900 ms 94320 KB Output is correct
15 Correct 932 ms 94300 KB Output is correct
16 Correct 906 ms 94364 KB Output is correct
17 Correct 919 ms 84232 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 17 ms 23756 KB Output is correct
3 Correct 18 ms 23844 KB Output is correct
4 Correct 17 ms 23804 KB Output is correct
5 Correct 17 ms 23788 KB Output is correct
6 Correct 19 ms 23788 KB Output is correct
7 Correct 18 ms 23912 KB Output is correct
8 Correct 19 ms 23884 KB Output is correct
9 Correct 17 ms 23792 KB Output is correct
10 Correct 28 ms 24740 KB Output is correct
11 Correct 26 ms 24804 KB Output is correct
12 Correct 23 ms 24644 KB Output is correct
13 Correct 24 ms 25044 KB Output is correct
14 Correct 22 ms 24988 KB Output is correct
15 Correct 25 ms 24860 KB Output is correct
16 Correct 1039 ms 84956 KB Output is correct
17 Correct 1162 ms 92300 KB Output is correct
18 Correct 1063 ms 87248 KB Output is correct
19 Correct 1031 ms 84004 KB Output is correct
20 Correct 994 ms 84296 KB Output is correct
21 Correct 910 ms 85356 KB Output is correct
22 Correct 934 ms 84020 KB Output is correct
23 Correct 773 ms 88668 KB Output is correct
24 Correct 685 ms 83848 KB Output is correct
25 Correct 751 ms 86704 KB Output is correct
26 Correct 701 ms 80052 KB Output is correct
27 Correct 737 ms 79188 KB Output is correct
28 Correct 946 ms 94256 KB Output is correct
29 Correct 900 ms 94320 KB Output is correct
30 Correct 932 ms 94300 KB Output is correct
31 Correct 906 ms 94364 KB Output is correct
32 Correct 919 ms 84232 KB Output is correct
33 Correct 1069 ms 87040 KB Output is correct
34 Correct 537 ms 73540 KB Output is correct
35 Correct 1066 ms 91444 KB Output is correct
36 Correct 1037 ms 86100 KB Output is correct
37 Correct 1025 ms 90296 KB Output is correct
38 Correct 1024 ms 87172 KB Output is correct
39 Correct 965 ms 104336 KB Output is correct
40 Correct 1066 ms 95892 KB Output is correct
41 Correct 814 ms 84616 KB Output is correct
42 Correct 715 ms 81204 KB Output is correct
43 Correct 1033 ms 92964 KB Output is correct
44 Correct 857 ms 86884 KB Output is correct
45 Correct 718 ms 101508 KB Output is correct
46 Correct 758 ms 100164 KB Output is correct
47 Correct 975 ms 94580 KB Output is correct
48 Correct 884 ms 94288 KB Output is correct
49 Correct 943 ms 94524 KB Output is correct
50 Correct 888 ms 94336 KB Output is correct
51 Correct 1181 ms 95820 KB Output is correct
52 Correct 1150 ms 95900 KB Output is correct