oj.uz

Submission #1021453

# Submission time Handle Problem Language Result Execution time Memory
1021453 2024-07-12T18:27:42 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 322344 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[i].size()<comps[j].size()){
                    swap(comps[i],comps[j]);
                }
                comps[i].push_back(i);
                comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
                for(int k:comps[i])
                    comp[k]=curr_comp;
            }
            comps[i].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]){
                    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 3 ms 5212 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 2 ms 5036 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 2 ms 5036 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 200 ms 88184 KB Output is correct
11 Correct 103 ms 49748 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 71 ms 35028 KB Output is correct
14 Correct 11 ms 7768 KB Output is correct
15 Correct 144 ms 66468 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 322344 KB Output is correct
2 Execution timed out 4050 ms 38408 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 2 ms 5036 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 200 ms 88184 KB Output is correct
11 Correct 103 ms 49748 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 71 ms 35028 KB Output is correct
14 Correct 11 ms 7768 KB Output is correct
15 Correct 144 ms 66468 KB Output is correct
16 Correct 1195 ms 322344 KB Output is correct
17 Execution timed out 4050 ms 38408 KB Time limit exceeded
18 Halted 0 ms 0 KB -