oj.uz

Submission #1020897

# Submission time Handle Problem Language Result Execution time Memory
1020897 2024-07-12T11:02:01 Z JakobZorz Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 94716 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>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;
    }
    vector<int>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);
    
    for(auto qry:srt){
        vector<bool>v1=reachable2(qry->S,qry->L);
        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 1 ms 5212 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 1 ms 4956 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 1 ms 5212 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 140 ms 31064 KB Output is correct
11 Correct 73 ms 21624 KB Output is correct
12 Correct 19 ms 6220 KB Output is correct
13 Correct 121 ms 69284 KB Output is correct
14 Correct 69 ms 69240 KB Output is correct
15 Correct 128 ms 23384 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5212 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 140 ms 31064 KB Output is correct
11 Correct 73 ms 21624 KB Output is correct
12 Correct 19 ms 6220 KB Output is correct
13 Correct 121 ms 69284 KB Output is correct
14 Correct 69 ms 69240 KB Output is correct
15 Correct 128 ms 23384 KB Output is correct
16 Execution timed out 4046 ms 94716 KB Time limit exceeded
17 Halted 0 ms 0 KB -