oj.uz

Submission #1021103

# Submission time Handle Problem Language Result Execution time Memory
1021103 2024-07-12T14:05:32 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 1198 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;
            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());
                comps[i].push_back(i);
            }
            comps[i].push_front(i);
            for(int j:comps[i])
                comp[j]=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 3 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 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 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 189 ms 87916 KB Output is correct
11 Correct 102 ms 49708 KB Output is correct
12 Correct 13 ms 9052 KB Output is correct
13 Correct 78 ms 45176 KB Output is correct
14 Correct 32 ms 45144 KB Output is correct
15 Correct 126 ms 66140 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 314536 KB Output is correct
2 Runtime error 357 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 3 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4960 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 189 ms 87916 KB Output is correct
11 Correct 102 ms 49708 KB Output is correct
12 Correct 13 ms 9052 KB Output is correct
13 Correct 78 ms 45176 KB Output is correct
14 Correct 32 ms 45144 KB Output is correct
15 Correct 126 ms 66140 KB Output is correct
16 Correct 1198 ms 314536 KB Output is correct
17 Runtime error 357 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -