oj.uz

Submission #471627

# Submission time Handle Problem Language Result Execution time Memory
471627 2021-09-10T04:36:27 Z Cross_Ratio Werewolf (IOI18_werewolf) C++14
49 / 100
 2185 ms 35388 KB 
#include <bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
const int INF = 1e9;
struct SegTree {
    struct Node {
        int ma, mi;
        Node(int m1, int m2) : ma(m1),mi(m2) {}
        Node(int v) : ma(v), mi(v) {}
        Node() : ma(-INF),mi(INF) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=2;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    Node f(Node x, Node y) {
        return Node(max(x.ma,y.ma),min(x.mi,y.mi));
    }
    void cons() {
        for(int i = MAX/2-1;i>0;i--) {
            seg[i] = f(seg[2*i],seg[2*i+1]);
        }
    }
    Node sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return Node();
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
    }
    Node sum(int s, int e) {
        return sum(s, e, 1, 0, MAX/2);
    }
    int LeftSmall(int s, int e, int k) {
        if(e == s + 1) {
            if(seg[s+MAX/2].ma <= k) return s;
            else return INF;
        }
        int mid = s + e >> 1;
        if(sum(s,mid).mi <= k) return LeftSmall(s,mid,k);
        return LeftSmall(mid,e,k);
    }
    int RightSmall(int s, int e, int k) {
        if(e == s + 1) {
            if(seg[s+MAX/2].ma <= k) return s;
            else return -INF;
        }
        int mid = s + e >> 1;
        if(sum(mid,e).mi <= k) return RightSmall(mid,e,k);
        return RightSmall(s,mid,k);
    }
    int LeftBig(int s, int e, int k) {
        if(e == s + 1) {
            if(seg[s+MAX/2].ma >= k) return s;
            else return INF;
        }
        int mid = s + e >> 1;
        if(sum(s,mid).ma >= k) return LeftBig(s,mid,k);
        return LeftBig(mid,e,k);
    }
    int RightBig(int s, int e, int k) {
        if(e == s + 1) {
            if(seg[s+MAX/2].ma >= k) return s;
            else return -INF;
        }
        int mid = s + e >> 1;
        if(sum(mid,e).ma >= k) return RightBig(mid,e,k);
        return RightBig(s,mid,k);
    }
};
typedef pair<int,int> P;
vector<vector<int> > adj;
vector<vector<P> > QueryL;
vector<vector<P> > QueryR;
int A[200005];
int B[200005];
struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n] < 0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        x = Find(x);
        y = Find(y);
        if(x == y) return;
        if(root[x] > root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    vector<int> ans;
    int Q = S.size();
    int M = X.size();
    if(N <= 3000 && M <= 6000 && Q <= 3000) {
        vector<vector<bool> > isCan1, isCan2;
        isCan1.resize(Q);
        isCan2.resize(Q);
        int i;
        for(i=0;i<Q;i++) {
            isCan1[i].resize(N);
            isCan2[i].resize(N);
        }
        adj.resize(N);
        for(i=0;i<M;i++) {
            adj[X[i]].push_back(Y[i]);
            adj[Y[i]].push_back(X[i]);
        }
        QueryL.resize(N);
        QueryR.resize(N);
        for(i=0;i<Q;i++) {
            QueryL[L[i]].push_back(P(S[i],i));
            QueryR[R[i]].push_back(P(E[i],i));
        }
        UnionFind UF1(N);
        for(i=N-1;i>=0;i--) {
            for(int n : adj[i]) {
                if(n > i) UF1.Merge(n, i);
            }
            for(P k : QueryL[i]) {
                for(int j = 0; j < N; j++) {
                    if(UF1.Find(j)==UF1.Find(k.first)) {
                        isCan1[k.second][j] = true;
                    }
                }
            }
        }
        UnionFind UF2(N);
        for(i = 0; i < N;i++) {
            for(int n : adj[i]) {
                if(n < i) UF2.Merge(n, i);
            }
            for(P k : QueryR[i]) {
                for(int j = 0; j <N; j++) {
                    if(UF2.Find(j) == UF2.Find(k.first)) {
                        isCan2[k.second][j] = true;
                    }
                }
            }
        }
        ans.resize(Q);
        for(i=0;i<Q;i++) {
            for(int j = 0; j < N;j++){
                if(isCan1[i][j] && isCan2[i][j]) ans[i] = 1;
            }
        }
        return ans;
    }
    adj.resize(N);
    int i;
    for(i=0;i<M;i++) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    int st;
    for(i=0;i<M;i++) {
        if(adj[i].size()==1) st = i;
    }
    int p = -1, c = st;
    i = 0;
    while(i != N) {
        A[i] = c;
        B[c] = i;
        for(int n : adj[c]) {
            if(n != p) {
                p = c;
                c = n;
                break;
            }
        }
        i++;
    }
    //for(i=0;i<N;i++) cout << A[i] << ' ';
    //cout << '\n';
    SegTree tree(N+5);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) {
        tree.seg[i+MAX/2].ma = A[i];
        tree.seg[i+MAX/2].mi = A[i];
    }
    tree.cons();
    for(i=0;i<Q;i++) {
        int x = B[S[i]];
        int y = B[E[i]];
        int l = L[i];
        int r = R[i];
        if(S[i] < L[i] || R[i] < E[i]) {
            ans.push_back(0);
            continue;
        }
        if(x < y) {
            int k1 = tree.LeftSmall(x, y+1, l-1) - 1;
            int k2 = tree.RightBig(x, y+1, r+1)+1;
            //cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
            if(k1 >= k2) ans.push_back(1);
            else ans.push_back(0);
        }
        else {
            int k1 = tree.LeftBig(y, x+1, r+1)-1;
            int k2 = tree.RightSmall(y, x + 1, l-1) + 1;
            //cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
            if(k1 >= k2) ans.push_back(1);
            else ans.push_back(0);
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In member function 'SegTree::Node SegTree::sum(int, int, int, int, int)':
werewolf.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
werewolf.cpp: In member function 'int SegTree::LeftSmall(int, int, int)':
werewolf.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = s + e >> 1;
      |                   ~~^~~
werewolf.cpp: In member function 'int SegTree::RightSmall(int, int, int)':
werewolf.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = s + e >> 1;
      |                   ~~^~~
werewolf.cpp: In member function 'int SegTree::LeftBig(int, int, int)':
werewolf.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = s + e >> 1;
      |                   ~~^~~
werewolf.cpp: In member function 'int SegTree::RightBig(int, int, int)':
werewolf.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = s + e >> 1;
      |                   ~~^~~
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:176:26: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |         for(int n : adj[c]) {
      |                          ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 135 ms 3608 KB Output is correct
11 Correct 142 ms 3460 KB Output is correct
12 Correct 108 ms 3436 KB Output is correct
13 Correct 122 ms 3464 KB Output is correct
14 Correct 112 ms 3452 KB Output is correct
15 Correct 154 ms 3560 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2019 ms 28512 KB Output is correct
2 Correct 2101 ms 28648 KB Output is correct
3 Correct 2185 ms 28488 KB Output is correct
4 Correct 2157 ms 28492 KB Output is correct
5 Correct 2054 ms 28680 KB Output is correct
6 Correct 2016 ms 28480 KB Output is correct
7 Correct 1890 ms 28580 KB Output is correct
8 Correct 2078 ms 28664 KB Output is correct
9 Correct 925 ms 28604 KB Output is correct
10 Correct 993 ms 28612 KB Output is correct
11 Correct 1166 ms 28516 KB Output is correct
12 Correct 1412 ms 28528 KB Output is correct
13 Correct 1962 ms 28520 KB Output is correct
14 Correct 1955 ms 28576 KB Output is correct
15 Correct 1947 ms 28524 KB Output is correct
16 Correct 2013 ms 28516 KB Output is correct
17 Correct 1982 ms 28636 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 135 ms 3608 KB Output is correct
11 Correct 142 ms 3460 KB Output is correct
12 Correct 108 ms 3436 KB Output is correct
13 Correct 122 ms 3464 KB Output is correct
14 Correct 112 ms 3452 KB Output is correct
15 Correct 154 ms 3560 KB Output is correct
16 Correct 2019 ms 28512 KB Output is correct
17 Correct 2101 ms 28648 KB Output is correct
18 Correct 2185 ms 28488 KB Output is correct
19 Correct 2157 ms 28492 KB Output is correct
20 Correct 2054 ms 28680 KB Output is correct
21 Correct 2016 ms 28480 KB Output is correct
22 Correct 1890 ms 28580 KB Output is correct
23 Correct 2078 ms 28664 KB Output is correct
24 Correct 925 ms 28604 KB Output is correct
25 Correct 993 ms 28612 KB Output is correct
26 Correct 1166 ms 28516 KB Output is correct
27 Correct 1412 ms 28528 KB Output is correct
28 Correct 1962 ms 28520 KB Output is correct
29 Correct 1955 ms 28576 KB Output is correct
30 Correct 1947 ms 28524 KB Output is correct
31 Correct 2013 ms 28516 KB Output is correct
32 Correct 1982 ms 28636 KB Output is correct
33 Incorrect 246 ms 35388 KB Output isn't correct
34 Halted 0 ms 0 KB -