oj.uz

Submission #803095

# Submission time Handle Problem Language Result Execution time Memory
803095 2023-08-02T21:40:21 Z gagik_2007 Werewolf (IOI18_werewolf) C++17
15 / 100
 158 ms 31376 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=300007;
ll n,m,k;
vector<int>g[N];
bool used[N];
bool used2[N];

void dfs1(int v, int btm){
    used[v]=true;
    for(int to:g[v]){
        if(!used[to]&&to>=btm){
            dfs1(to,btm);
        }
    }
}

bool dfs2(int v, int top){
    if(used[v])return true;
    used2[v]=true;
    for(int to:g[v]){
        if(!used2[to]&&to<=top){
            if(dfs2(to,top)){
                return true;
            }
        }
    }
    return false;
}

vector<int> check_validity(int NN, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n=NN;
    m=X.size();
    k=S.size();
    for(int i=0;i<m;i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector<int>ans;
    if(n<=3000&&k<=3000&&m<=6000){
        for(int i=0;i<k;i++){
            dfs1(S[i],L[i]);
            ans.push_back(dfs2(E[i],R[i]));
            fill(used,used+n+1,false);
            fill(used2,used2+n+1,false);
        }
        return ans;
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 4 ms 7356 KB Output is correct
6 Correct 4 ms 7356 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7308 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 4 ms 7356 KB Output is correct
6 Correct 4 ms 7356 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7308 KB Output is correct
10 Correct 116 ms 7728 KB Output is correct
11 Correct 69 ms 7720 KB Output is correct
12 Correct 12 ms 7892 KB Output is correct
13 Correct 105 ms 7768 KB Output is correct
14 Correct 88 ms 7700 KB Output is correct
15 Correct 158 ms 7888 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 31376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7356 KB Output is correct
5 Correct 4 ms 7356 KB Output is correct
6 Correct 4 ms 7356 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7308 KB Output is correct
10 Correct 116 ms 7728 KB Output is correct
11 Correct 69 ms 7720 KB Output is correct
12 Correct 12 ms 7892 KB Output is correct
13 Correct 105 ms 7768 KB Output is correct
14 Correct 88 ms 7700 KB Output is correct
15 Correct 158 ms 7888 KB Output is correct
16 Incorrect 127 ms 31376 KB Output isn't correct
17 Halted 0 ms 0 KB -