oj.uz

Submission #1021565

# Submission time Handle Problem Language Result Execution time Memory
1021565 2024-07-12T19:54:28 Z JakobZorz Werewolf (IOI18_werewolf) C++17
49 / 100
 807 ms 169156 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<vector<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){
                if(comps[curr_comp].size()<comps[j].size()){
                    swap(curr_comp,j);
                }
                comps[curr_comp].push_back(i);
                comp[i]=curr_comp;
                comps[curr_comp].insert(comps[curr_comp].end(),comps[j].begin(),comps[j].end());
                for(int k:comps[j])
                    comp[k]=curr_comp;
            }
            comps[curr_comp].push_back(i);
        }
        line=comps[comp[0]];
    }
    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]){
                    int br=r;
                    if(comps[comp[r]].size()<comps[comp[ne]].size())
                        swap(ne,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[comp[r]].insert(i);
                    for(int i:comps[comp[ne]])
                        comp[i]=comp[r];
                    r=br;
                }
            }
            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 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 5172 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 5172 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 7 ms 6748 KB Output is correct
11 Correct 7 ms 6748 KB Output is correct
12 Correct 7 ms 7260 KB Output is correct
13 Correct 8 ms 6844 KB Output is correct
14 Correct 8 ms 7004 KB Output is correct
15 Correct 8 ms 6936 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 158112 KB Output is correct
2 Correct 524 ms 127944 KB Output is correct
3 Correct 581 ms 140220 KB Output is correct
4 Correct 646 ms 156888 KB Output is correct
5 Correct 667 ms 160096 KB Output is correct
6 Correct 764 ms 165432 KB Output is correct
7 Correct 753 ms 169156 KB Output is correct
8 Correct 555 ms 127708 KB Output is correct
9 Correct 458 ms 140120 KB Output is correct
10 Correct 512 ms 156732 KB Output is correct
11 Correct 555 ms 158200 KB Output is correct
12 Correct 594 ms 165264 KB Output is correct
13 Correct 529 ms 120340 KB Output is correct
14 Correct 527 ms 120592 KB Output is correct
15 Correct 541 ms 120304 KB Output is correct
16 Correct 521 ms 120380 KB Output is correct
17 Correct 739 ms 167048 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 5172 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 7 ms 6748 KB Output is correct
11 Correct 7 ms 6748 KB Output is correct
12 Correct 7 ms 7260 KB Output is correct
13 Correct 8 ms 6844 KB Output is correct
14 Correct 8 ms 7004 KB Output is correct
15 Correct 8 ms 6936 KB Output is correct
16 Correct 807 ms 158112 KB Output is correct
17 Correct 524 ms 127944 KB Output is correct
18 Correct 581 ms 140220 KB Output is correct
19 Correct 646 ms 156888 KB Output is correct
20 Correct 667 ms 160096 KB Output is correct
21 Correct 764 ms 165432 KB Output is correct
22 Correct 753 ms 169156 KB Output is correct
23 Correct 555 ms 127708 KB Output is correct
24 Correct 458 ms 140120 KB Output is correct
25 Correct 512 ms 156732 KB Output is correct
26 Correct 555 ms 158200 KB Output is correct
27 Correct 594 ms 165264 KB Output is correct
28 Correct 529 ms 120340 KB Output is correct
29 Correct 527 ms 120592 KB Output is correct
30 Correct 541 ms 120304 KB Output is correct
31 Correct 521 ms 120380 KB Output is correct
32 Correct 739 ms 167048 KB Output is correct
33 Correct 724 ms 134168 KB Output is correct
34 Correct 202 ms 45436 KB Output is correct
35 Correct 733 ms 124464 KB Output is correct
36 Incorrect 726 ms 136008 KB Output isn't correct
37 Halted 0 ms 0 KB -