oj.uz

Submission #1021060

# Submission time Handle Problem Language Result Execution time Memory
1021060 2024-07-12T13:31:02 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 114384 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 1e9;
        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(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()+1;
            while(l<r-1){
                int mid=(l+r)/2;
                if(rmq.get(i,mid)<=qry->R)
                    l=mid;
                else
                    r=mid;
            }
            rr=l;
            //cout<<rr<<" "<<l<<" "<<i<<" "<<line.size()<<"\n";
        }
        
        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;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:156:18: warning: 'rl' may be used uninitialized in this function [-Wmaybe-uninitialized]
  156 |             if(rl<i&&i<rr)
      |                ~~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 3 ms 5136 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 5208 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 3 ms 5136 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 220 ms 88400 KB Output is correct
11 Correct 132 ms 49748 KB Output is correct
12 Correct 18 ms 8540 KB Output is correct
13 Correct 114 ms 75232 KB Output is correct
14 Correct 50 ms 69356 KB Output is correct
15 Correct 154 ms 66384 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 114384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 4 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 3 ms 5136 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 220 ms 88400 KB Output is correct
11 Correct 132 ms 49748 KB Output is correct
12 Correct 18 ms 8540 KB Output is correct
13 Correct 114 ms 75232 KB Output is correct
14 Correct 50 ms 69356 KB Output is correct
15 Correct 154 ms 66384 KB Output is correct
16 Execution timed out 4038 ms 114384 KB Time limit exceeded
17 Halted 0 ms 0 KB -