oj.uz

Submission #800237

# Submission time Handle Problem Language Result Execution time Memory
800237 2023-08-01T12:35:16 Z jasmin Werewolf (IOI18_werewolf) C++17
34 / 100
 1534 ms 37956 KB 
//#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

const int INF=1e9+7;

struct node{
    int maxi=0;
    int mini=INF;
};
node none={0, INF};

struct segtree{
    vector<node> tree;

    segtree(int n){
        tree.assign(n*4, none);
    }

    node merge(node a, node b){
        a.maxi = max(a.maxi, b.maxi);
        a.mini = min(a.mini, b.mini);
        return a;
    }

    node update(int l, int r, int v, int x, int val){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]={val, val};
        }
        int m=l+(r-l)/2;
        return tree[v] = merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
    }

    node query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return none;
        if(ql<=l && r<=qr){
            return tree[v];
        }
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};

bool line_query(int n, segtree& seg, int a, int b, int left, int right, bool reverse){

    int l=a; int r=b;
    int ans=-1;
    while(l<=r){
        int m=l+(r-l)/2;

        auto x=seg.query(0, n, 0, a, m+1);
        if((!reverse && left <= x.mini) || (reverse && x.maxi<=right)){
            ans = m;
            l = m+1;
        }
        else{
            r=m-1;
        }
    }
    int lastr=ans;

    l=a;  r=b;
    ans=n;
    while(l<=r){
        int m=l+(r-l)/2;

        auto x=seg.query(0, n, 0, m, b+1);
        if((!reverse && x.maxi <= right) || (reverse && left <= x.mini)){
            ans = m;
            r = m-1;
        }
        else{
            l = m+1;
        }
    }
    int lastl=ans;

    return lastl <= lastr;
}

vector<int> solve_line(int n, vector<vector<int> >& adi, vector<int>& s, vector<int>& e,
                        vector<int>& l, vector<int>& r){

    //find line
    vector<int> line;
    int start=0;
    for(int v=0; v<n; v++){

        if(adi[v].size()==1){
            start=v;
        }
    }
 
    int v=start; int p=-1;
    for(int i=0; i<n; i++){

        line.push_back(v);

        for(auto u: adi[v]){

            if(u!=p){

                p=v;
                v=u;
                break;
            }
        }

    }

    vector<int> ind(n);
    for(int i=0; i<n; i++){
        ind[line[i]]=i;
    }

    //initialize segtree
    segtree seg(n);
    for(int i=0; i<n; i++){

        seg.update(0, n, 0, i, line[i]);
    }


    //answer queries
    int q=s.size();
    vector<int> ans(q);
    for(int i=0; i<q; i++){
        int a=ind[s[i]]; int b=ind[e[i]];

        bool reverse=false;
        if(b<a){
            swap(a, b);
            reverse = true;
        }

        ans[i] = line_query(n, seg, a, b, l[i], r[i], reverse);
    }

    return ans;
}

vector<int> check_validity(int n, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {

    int m=x.size();

    vector<vector<int> > adi(n);
    for(int i=0; i<m; i++){
        adi[x[i]].push_back(y[i]);
        adi[y[i]].push_back(x[i]);
    }

    return solve_line(n, adi, s, e, l, r);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1412 ms 29420 KB Output is correct
2 Correct 1492 ms 37880 KB Output is correct
3 Correct 1491 ms 37848 KB Output is correct
4 Correct 1486 ms 37848 KB Output is correct
5 Correct 1484 ms 37760 KB Output is correct
6 Correct 1429 ms 37884 KB Output is correct
7 Correct 1507 ms 37952 KB Output is correct
8 Correct 1490 ms 37852 KB Output is correct
9 Correct 628 ms 37860 KB Output is correct
10 Correct 781 ms 37828 KB Output is correct
11 Correct 936 ms 37940 KB Output is correct
12 Correct 1008 ms 37932 KB Output is correct
13 Correct 1483 ms 37848 KB Output is correct
14 Correct 1496 ms 37952 KB Output is correct
15 Correct 1484 ms 37848 KB Output is correct
16 Correct 1476 ms 37956 KB Output is correct
17 Correct 1534 ms 37848 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -