oj.uz

Submission #1021092

# Submission time Handle Problem Language Result Execution time Memory
1021092 2024-07-12T13:54:56 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 1299 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<vector<int>>comps(n);
        
        for(int i=0;i<n;i++){
            comps[i]={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);
            }
            for(int j:comps[i])
                comp[j]=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;
        }
        
        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 4 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 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 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 4 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 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 3 ms 5212 KB Output is correct
10 Correct 212 ms 88220 KB Output is correct
11 Correct 116 ms 49748 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 103 ms 75404 KB Output is correct
14 Correct 48 ms 69460 KB Output is correct
15 Correct 148 ms 66388 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1299 ms 321132 KB Output is correct
2 Runtime error 434 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 3 ms 5212 KB Output is correct
2 Correct 4 ms 5140 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 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 3 ms 5212 KB Output is correct
10 Correct 212 ms 88220 KB Output is correct
11 Correct 116 ms 49748 KB Output is correct
12 Correct 10 ms 8536 KB Output is correct
13 Correct 103 ms 75404 KB Output is correct
14 Correct 48 ms 69460 KB Output is correct
15 Correct 148 ms 66388 KB Output is correct
16 Correct 1299 ms 321132 KB Output is correct
17 Runtime error 434 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -