oj.uz

Submission #590050

# Submission time Handle Problem Language Result Execution time Memory
590050 2022-07-05T13:45:33 Z Dremix10 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 36180 KB 
#include "werewolf.h"
#include <iostream>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
//const int N = 3e5+1;

vector<int> par,siz,vis;


int find(int x){
    return (par[x] == x) ? x : par[x] = find(par[x]);
}

void join(int x, int y){
    x = find(x);
    y = find(y);
    if(x==y)return;
    if(siz[y] > siz[x])
        swap(x,y);
    par[y] = x;
    siz[x] += siz[y];
}

vector<vector<int> > a;
int use;
bool flag;
int l,r;


void dfs(int s){
    vis[s] = use;
    for(auto x : a[s]){
        if(use == 1 && x < l)continue;
        if(use == 2 && x > r)continue;

        if(!vis[x])dfs(x);
        if(vis[x] == 1 && use == 2){
            flag = true;
        }
    }

}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
    par.resize(N);
    siz.resize(N);
    vis.resize(N);
    a.assign(N,vector<int>());
    
    int q = S.size();
    int m = X.size();

    int i,k;

    for(i=0;i<m;i++){
        int x = X[i], y = Y[i];
        a[x].push_back(y);
        a[y].push_back(x);
    }

    vector<int> ans;

    for(k=0;k<q;k++){
        int s = S[k], e = E[k];
        l = L[k];
        r = R[k];

        iota(all(par),0);
        fill(all(siz),1);
        fill(all(vis),0);

        use = 1;
        flag = false;
        dfs(s);

        use = 2;

        if(vis[e] == 1)flag = true;
        dfs(e);

        ans.push_back(flag);

    }


    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 188 ms 784 KB Output is correct
11 Correct 122 ms 752 KB Output is correct
12 Correct 17 ms 848 KB Output is correct
13 Correct 225 ms 888 KB Output is correct
14 Correct 199 ms 736 KB Output is correct
15 Correct 225 ms 888 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 36180 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 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 188 ms 784 KB Output is correct
11 Correct 122 ms 752 KB Output is correct
12 Correct 17 ms 848 KB Output is correct
13 Correct 225 ms 888 KB Output is correct
14 Correct 199 ms 736 KB Output is correct
15 Correct 225 ms 888 KB Output is correct
16 Execution timed out 4050 ms 36180 KB Time limit exceeded
17 Halted 0 ms 0 KB -