Submission #471627

#	Time	Username	Problem	Language	Result	Execution time	Memory
471627		Cross_Ratio	Werewolf (IOI18_werewolf)	C++14	49 / 100	2185 ms	35388 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51