oj.uz

Submission #1015382

# Submission time Handle Problem Language Result Execution time Memory
1015382 2024-07-06T09:53:49 Z nisanduu Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 24332 KB 
#include <bits/stdc++.h> 
// #include "werewolf.h"
using namespace std;
typedef int ll;

// 0 - Wolf
// 1 - Human

vector<int> check_validity(int	N,	vector<int>	X,	vector<int>	Y,	vector<int>	S,	vector<int>	E,	vector<int>
	L,	vector<int>	R){
        
    
        vector<vector<ll>> adj(N+1);
        ll M = X.size();
        for(ll i=0;i<M;i++){
            adj[X[i]].push_back(Y[i]);
            adj[Y[i]].push_back(X[i]);
        }
        
        ll Q = S.size();
        vector<int> ans(Q);
        for(ll i=0;i<Q;i++){
            vector<int> vis(N+1),vis1(N+1),arr(N+1);

            queue<ll> q,q1;
            q.push(S[i]);
            while(!q.empty()){
                ll node = q.front();
                q.pop();
                if(vis[node]==1) continue;
                arr[node]=1;
                vis[node]=1;
                for(auto el:adj[node]){
                    if(!vis[el]&&el>=L[i]){
                        q.push(el);
                    }
                }
            }
            q1.push(E[i]);
            while(!q1.empty()){
                ll node = q1.front();
                q1.pop();
                if(vis1[node]==1) continue;
                arr[node]+=1;
                vis1[node]=1;
                for(auto el:adj[node]){
                    if(!vis1[el]&&el<=R[i]){
                        q1.push(el);
                    }
                }
            }
            for(ll j=0;j<N;j++){
                if(arr[j]!=S[i]&&j>=L[i]&&arr[j]==2&&j<=R[i]){
                    ans[i]=1;
                }
            }
            // for(ll j=S[i]+1;j<=N;j++){
            //     // if(arr[j]==2&&j>=L[i]&&j<=R[i]){
            //     //     ans[i]=1;
            //     // }
            //     cout<<arr[j]<<endl;
            // }
            //break;
        }
        return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 24332 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 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -