oj.uz

Submission #1021108

# Submission time Handle Problem Language Result Execution time Memory
1021108 2024-07-12T14:08:01 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 1347 ms 524288 KB 
#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
 
int n,m,q;
vector<int>nodes[200000];
 
struct RMQ{
    vector<vector<int>>table;
    vector<int>lg2;
    int n;
    RMQ(vector<int>arr){
        n=(int)arr.size();
        table=vector<vector<int>>(20,vector<int>(n));
        int curr=1;
        lg2=vector<int>(n+1);
        for(int i=2;i<=n;i++){
            while((1<<curr)<=i)
                curr++;
            lg2[i]=curr-1;
        }
        table[0]=arr;
        for(int p=1;p<20;p++){
            for(int i=0;i+(1<<p)<=n;i++){
                table[p][i]=max(table[p-1][i],table[p-1][i+(1<<(p-1))]);
            }
        }
    }
    
    int get(int l,int r){
        if(l==r)
            return 0;
        int lg=lg2[r-l];
        return max(table[lg][l],table[lg][r-(1<<lg)]);
    }
};
 
struct Query{
    int S,E,L,R;
    int ans;
};
 
bool cmp(Query*a,Query*b){
    return a->L>b->L;
}
 
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
    n=N;
    m=(int)X.size();
    q=(int)S.size();
    for(int i=0;i<n;i++){
        nodes[i].clear();
    }
    for(int i=0;i<m;i++){
        nodes[X[i]].push_back(Y[i]);
        nodes[Y[i]].push_back(X[i]);
    }
    
    vector<int>line;
    {
        vector<int>comp(n);
        vector<deque<int>>comps(n);
        
        for(int i=0;i<n;i++){
            set<int>to_add;
            int curr_comp=i;
            comp[i]=i;
            for(int ne:nodes[i]){
                if(ne>i)
                    continue;
                to_add.insert(comp[ne]);
            }
            for(int j:to_add){
                comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
                for(int k:comps[j])
                    comp[k]=curr_comp;
                comps[i].push_back(i);
            }
            comps[i].push_front(i);
        }
        line=vector<int>(comps[comp[0]].begin(),comps[comp[0]].end());
    }
    vector<int>to_line(n);
    for(int i=0;i<(int)line.size();i++){
        to_line[line[i]]=i;
    }
    
    RMQ rmq=RMQ(line);
    /*for(int i:line)
        cout<<i<<" ";
    cout<<"\n";*/
    
    vector<Query*>qrs(q);
    
    for(int i=0;i<q;i++){
        qrs[i]=new Query;
        qrs[i]->S=S[i];
        qrs[i]->E=E[i];
        qrs[i]->L=L[i];
        qrs[i]->R=R[i];
        qrs[i]->ans=0;
    }
    
    vector<Query*>srt=qrs;
    sort(srt.begin(),srt.end(),cmp);
    
    vector<int>comp(n);
    vector<vector<int>>comps(n);
    vector<set<int>>comps_line(n);
    
    int r=n-1;
    for(auto qry:srt){
        while(r>=qry->L){
            comp[r]=r;
            comps[r]={r};
            comps_line[r].insert(to_line[r]);
            for(int ne:nodes[r]){
                if(ne<r)
                    continue;
                if(comp[ne]!=comp[r]){
                    comps[comp[r]].insert(comps[comp[r]].end(),comps[comp[ne]].begin(),comps[comp[ne]].end());
                    for(int i:comps_line[comp[ne]])
                        comps_line[r].insert(i);
                    for(int i:comps[comp[r]])
                        comp[i]=comp[r];
                }
            }
            r--;
        }
        
        int rl,rr;
        /*for(int j=0;j<(int)line.size();j++){
            if(line[j]==qry->E){
                //for(rr=j;rr<(int)line.size()&&line[rr]<=qry->R;rr++);
                //for(rl=j;rl>=0&&line[rl]<=qry->R;rl--);
                break;
            }
        }*/
        
        {
            int i=to_line[qry->E];
            int l=i,r=(int)line.size();
            while(l<r-1){
                int mid=(l+r)/2;
                if(rmq.get(i,mid+1)<=qry->R)
                    l=mid;
                else
                    r=mid;
            }
            rr=r;
        }
        
        {
            int i=to_line[qry->E];
            int l=0,r=i;
            while(l<r-1){
                int mid=(l+r)/2;
                if(rmq.get(mid,i)<=qry->R)
                    r=mid;
                else
                    l=mid;
            }
            rl=l;
        }
        
        auto iter=comps_line[comp[qry->S]].lower_bound(rl+1);
        if(iter!=comps_line[comp[qry->S]].end()&&*iter<rr)
            qry->ans=1;
        
        /*for(int i:comps_line[comp[qry->S]]){
            if(rl<i&&i<rr)
                qry->ans=1;
        }*/
    }
    
    vector<int>res(q);
    for(int i=0;i<q;i++)
        res[i]=qrs[i]->ans;
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5136 KB Output is correct
9 Correct 2 ms 5288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5136 KB Output is correct
9 Correct 2 ms 5288 KB Output is correct
10 Correct 200 ms 88156 KB Output is correct
11 Correct 126 ms 49804 KB Output is correct
12 Correct 10 ms 9052 KB Output is correct
13 Correct 92 ms 45360 KB Output is correct
14 Correct 34 ms 45300 KB Output is correct
15 Correct 143 ms 66396 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1347 ms 314720 KB Output is correct
2 Runtime error 383 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 3 ms 5136 KB Output is correct
9 Correct 2 ms 5288 KB Output is correct
10 Correct 200 ms 88156 KB Output is correct
11 Correct 126 ms 49804 KB Output is correct
12 Correct 10 ms 9052 KB Output is correct
13 Correct 92 ms 45360 KB Output is correct
14 Correct 34 ms 45300 KB Output is correct
15 Correct 143 ms 66396 KB Output is correct
16 Correct 1347 ms 314720 KB Output is correct
17 Runtime error 383 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -