oj.uz

Submission #1020902

# Submission time Handle Problem Language Result Execution time Memory
1020902 2024-07-12T11:12:14 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 93212 KB 
#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;

int n,m,q;
vector<int>nodes[200000];

vector<bool>reachable2(int s,int t){
    vector<bool>vis(n);
    queue<int>q;
    q.push(s);
    while(q.size()){
        int node=q.front();
        q.pop();
        if(vis[node]||node<t)
            continue;
        vis[node]=true;
        for(int ne:nodes[node])
            q.push(ne);
    }
    return vis;
}

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]];
    }
    /*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);
    
    int r=n-1;
    for(auto qry:srt){
        while(r>=qry->L){
            comp[r]=r;
            comps[r]={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[comp[r]])
                        comp[i]=comp[r];
                }
            }
            r--;
        }
        
        //vector<bool>v1=reachable2(qry->S,qry->L);
        vector<bool>v1(n);
        for(int i:comps[comp[qry->S]])
            v1[i]=true;
        vector<bool>v2(n);
        for(int j=0;j<(int)line.size();j++){
            if(line[j]==qry->E){
                for(int k=j;k<(int)line.size()&&line[k]<=qry->R;k++)
                    v2[line[k]]=true;
                for(int k=j;k>=0&&line[k]<=qry->R;k--)
                    v2[line[k]]=true;
                break;
            }
        }
        for(int j=0;j<n;j++)
            if(v1[j]&&v2[j])
                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 5208 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 5204 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 5204 KB Output is correct
10 Correct 51 ms 33108 KB Output is correct
11 Correct 41 ms 22292 KB Output is correct
12 Correct 20 ms 6232 KB Output is correct
13 Correct 70 ms 69408 KB Output is correct
14 Correct 69 ms 69456 KB Output is correct
15 Correct 44 ms 23532 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4952 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 1 ms 5204 KB Output is correct
10 Correct 51 ms 33108 KB Output is correct
11 Correct 41 ms 22292 KB Output is correct
12 Correct 20 ms 6232 KB Output is correct
13 Correct 70 ms 69408 KB Output is correct
14 Correct 69 ms 69456 KB Output is correct
15 Correct 44 ms 23532 KB Output is correct
16 Execution timed out 4059 ms 93212 KB Time limit exceeded
17 Halted 0 ms 0 KB -