oj.uz

Submission #727928

# Submission time Handle Problem Language Result Execution time Memory
727928 2023-04-21T15:30:57 Z nguyentunglam Werewolf (IOI18_werewolf) C++17
100 / 100
 1322 ms 206752 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define ii pair<int, int>
using namespace std;

const int N = 6e5 + 10;
vector<ii> e1[N], e2[N];
int cnt;
vector<tuple<int, int, int, int> > query[N];

struct kruskal {
    int par[20][N], w[N], timer, lst[N];
    int st[N], ed[N];
    vector<int> ad[N];

    int root(int v) {
        return par[0][v] < 0 ? v : par[0][v] = root(par[0][v]);
    }

    void join(int u, int v, int c) {
        u = root(u); v = root(v);
        if (u == v) return;
        ++cnt;
        ad[cnt].push_back(u);
        ad[cnt].push_back(v);
        par[0][cnt] = -1; w[cnt] = c;
        par[0][u] = cnt; par[0][v] = cnt;
    }

    void dfs(int u) {
        st[u] = ++timer;
        lst[timer] = u;
        for(int j = 1; j <= 19; j++) {
            if (par[j - 1][u] < 0) par[j][u] = -1;
            else par[j][u] = par[j - 1][par[j - 1][u]];
        }
        for(int &v : ad[u]) {
            par[0][v] = u;
            dfs(v);
        }
        ed[u] = timer;
    }

    int get(int u, int cost, int type) {
        for(int j = 19; j >= 0; j--) {
            int p = par[j][u];
            if (p <= 0) continue;
            if (!type && w[p] <= cost) u = p;
            else if (type && w[p] >= cost) u = p;
        }
        return u;
    }

} T[2];

int bit[N];
void up(int pos, int val) {
    while (pos <= 6e5) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

int getrange(int l, int r) {
    return get(r) - get(l - 1);
}

vector<int> check_validity (int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    cnt = n - 1;

    for(int i = 0; i < x.size(); i++) {
        int u = x[i], v = y[i];
        e1[min(u, v)].emplace_back(u, v);
        e2[max(u, v)].emplace_back(u, v);
    }

    for(int i = 0; i < n; i++) T[0].par[0][i] = T[1].par[0][i] = -1;

    for(int i = 0; i < n; i++) for(auto &it : e2[i]) {
        T[0].join(it.fi, it.se, i);
    }
    for(int i = 0; i <= cnt; i++) if (T[0].par[0][i] < 0) T[0].dfs(i);
    for(int i = n - 1; i >= 0; i--) for(auto &it : e1[i]) {
        T[1].join(it.fi, it.se, i);
    }
    for(int i = 0; i <= cnt; i++) if (T[1].par[0][i] < 0) T[1].dfs(i);
    vector<int> ans;
    ans.resize(s.size());

    for(int i = 0; i < s.size(); i++) {
        int p1 = T[1].get(s[i], l[i], 1);
        int p2 = T[0].get(e[i], r[i], 0);
//        cout << p1 << " " << p2 << " " << T[0].w[p2] << " " << r[i] << endl;
        query[T[1].ed[p1]].emplace_back(T[0].st[p2], T[0].ed[p2], i, 1);
        query[T[1].st[p1] - 1].emplace_back(T[0].st[p2], T[0].ed[p2], i, -1);
    }

    for(int i = 0; i <= T[1].timer; i++) {
        int u = T[1].lst[i];
        if (u < n) up(T[0].st[u], 1);
        for(auto &it : query[i]) {
            int L, R, id, sign; tie(L, R, id, sign) = it;
            ans[id] += sign * getrange(L, R);
        }
    }

    for(int &i : ans) {
        i = (i > 0);
    }
    return ans;
}
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define pb push_back
#ifdef ngu
#define forv(a, b) for(auto &a : b)
int main() {
    #define task "task"
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    vector<int> x,y,st,ed,lf,rt;
    int n,m,q; cin>>n>>m>>q;
    forinc(i,1,m){
        x.pb(in),y.pb(in);
    }

    forinc(i,1,q){
        st.pb(in), ed.pb(in), lf.pb(in), rt.pb(in);
//        if (i == 82) cout << st.back() << " " << ed.back() << " " << lf.back() << " " << rt.back() << endl;
    }
    forv(i,check_validity(n,x,y,st,ed,lf,rt)) cout<<i<<"\n";
}
#endif // ngu

Compilation message

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:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~
werewolf.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71252 KB Output is correct
2 Correct 35 ms 71128 KB Output is correct
3 Correct 35 ms 71096 KB Output is correct
4 Correct 34 ms 71132 KB Output is correct
5 Correct 33 ms 71252 KB Output is correct
6 Correct 34 ms 71116 KB Output is correct
7 Correct 34 ms 71236 KB Output is correct
8 Correct 35 ms 71224 KB Output is correct
9 Correct 35 ms 71116 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71252 KB Output is correct
2 Correct 35 ms 71128 KB Output is correct
3 Correct 35 ms 71096 KB Output is correct
4 Correct 34 ms 71132 KB Output is correct
5 Correct 33 ms 71252 KB Output is correct
6 Correct 34 ms 71116 KB Output is correct
7 Correct 34 ms 71236 KB Output is correct
8 Correct 35 ms 71224 KB Output is correct
9 Correct 35 ms 71116 KB Output is correct
10 Correct 40 ms 73080 KB Output is correct
11 Correct 41 ms 73132 KB Output is correct
12 Correct 44 ms 72984 KB Output is correct
13 Correct 41 ms 73164 KB Output is correct
14 Correct 39 ms 73164 KB Output is correct
15 Correct 40 ms 73264 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 999 ms 191272 KB Output is correct
2 Correct 978 ms 198168 KB Output is correct
3 Correct 967 ms 195356 KB Output is correct
4 Correct 829 ms 193696 KB Output is correct
5 Correct 818 ms 193804 KB Output is correct
6 Correct 872 ms 195264 KB Output is correct
7 Correct 814 ms 193580 KB Output is correct
8 Correct 855 ms 198296 KB Output is correct
9 Correct 603 ms 194352 KB Output is correct
10 Correct 474 ms 193708 KB Output is correct
11 Correct 504 ms 193452 KB Output is correct
12 Correct 621 ms 193452 KB Output is correct
13 Correct 1104 ms 202812 KB Output is correct
14 Correct 1161 ms 202804 KB Output is correct
15 Correct 1139 ms 202956 KB Output is correct
16 Correct 1110 ms 202908 KB Output is correct
17 Correct 788 ms 193224 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71252 KB Output is correct
2 Correct 35 ms 71128 KB Output is correct
3 Correct 35 ms 71096 KB Output is correct
4 Correct 34 ms 71132 KB Output is correct
5 Correct 33 ms 71252 KB Output is correct
6 Correct 34 ms 71116 KB Output is correct
7 Correct 34 ms 71236 KB Output is correct
8 Correct 35 ms 71224 KB Output is correct
9 Correct 35 ms 71116 KB Output is correct
10 Correct 40 ms 73080 KB Output is correct
11 Correct 41 ms 73132 KB Output is correct
12 Correct 44 ms 72984 KB Output is correct
13 Correct 41 ms 73164 KB Output is correct
14 Correct 39 ms 73164 KB Output is correct
15 Correct 40 ms 73264 KB Output is correct
16 Correct 999 ms 191272 KB Output is correct
17 Correct 978 ms 198168 KB Output is correct
18 Correct 967 ms 195356 KB Output is correct
19 Correct 829 ms 193696 KB Output is correct
20 Correct 818 ms 193804 KB Output is correct
21 Correct 872 ms 195264 KB Output is correct
22 Correct 814 ms 193580 KB Output is correct
23 Correct 855 ms 198296 KB Output is correct
24 Correct 603 ms 194352 KB Output is correct
25 Correct 474 ms 193708 KB Output is correct
26 Correct 504 ms 193452 KB Output is correct
27 Correct 621 ms 193452 KB Output is correct
28 Correct 1104 ms 202812 KB Output is correct
29 Correct 1161 ms 202804 KB Output is correct
30 Correct 1139 ms 202956 KB Output is correct
31 Correct 1110 ms 202908 KB Output is correct
32 Correct 788 ms 193224 KB Output is correct
33 Correct 1225 ms 196480 KB Output is correct
34 Correct 307 ms 114788 KB Output is correct
35 Correct 1284 ms 199364 KB Output is correct
36 Correct 1209 ms 196316 KB Output is correct
37 Correct 1322 ms 198552 KB Output is correct
38 Correct 1253 ms 196916 KB Output is correct
39 Correct 1095 ms 203588 KB Output is correct
40 Correct 1029 ms 206012 KB Output is correct
41 Correct 830 ms 196572 KB Output is correct
42 Correct 680 ms 194540 KB Output is correct
43 Correct 1114 ms 204248 KB Output is correct
44 Correct 1012 ms 198120 KB Output is correct
45 Correct 734 ms 201900 KB Output is correct
46 Correct 762 ms 202432 KB Output is correct
47 Correct 1148 ms 202980 KB Output is correct
48 Correct 1224 ms 202856 KB Output is correct
49 Correct 1134 ms 202988 KB Output is correct
50 Correct 1152 ms 202828 KB Output is correct
51 Correct 875 ms 206288 KB Output is correct
52 Correct 870 ms 206752 KB Output is correct