Submission #471597

#	Time	Username	Problem	Language	Result	Execution time	Memory
471597		Cross_Ratio	Werewolf (IOI18_werewolf)	C++14	0 / 100	2083 ms	27476 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 -1;
        }
        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 -1;
        }
        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 -1;
        }
        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 -1;
        }
        int mid = s + e >> 1;
        if(sum(mid,e).mi < k) return RightBig(mid,e,k);
        return RightBig(s,mid,k);
    }
};
vector<vector<int> > adj;
int A[200005];
int B[200005];
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();
    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(x < y) {
            int k1 = tree.RightBig(x, y+1, l);
            int k2 = tree.LeftSmall(x, y+1, r);
            //cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
            if(k1 <= k2) ans.push_back(1);
            else ans.push_back(0);
        }
        else {
            int k1 = tree.RightSmall(y, x+1, r);
            int k2 = tree.LeftBig(y, x + 1, l);
            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:98:26: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |         for(int n : adj[c]) {
      |                          ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51