oj.uz

Submission #313633

# Submission time Handle Problem Language Result Execution time Memory
313633 2020-10-16T13:16:24 Z talant117408 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 35544 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 2e5+7;
vector <vector <int>> graph(N);
vector <int> eq, vis, belong, cluster, can, can2;
int n, q, clcnt;

void go(int v, int cond){
    vis[v] = 1;
    if(cluster[belong[v]] == 1){
        if(!cond) can[belong[v]] = 1;
        else can2[belong[v]] = 1;
    }
    
    for(auto to : graph[v]){
        if(!vis[to] && (cond != cluster[belong[to]])){
            go(to, cond);
        }
    }
}

void findcl(int v){
    cluster[clcnt] = eq[v];
    belong[v] = clcnt;
    vis[v] = 1;
    
    for(auto to : graph[v]){
        if(!vis[to] && eq[to] == eq[v]){
            findcl(to);
        }
    }
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R){
    
    int i, j;
    n = N, q = sz(S);
    vector <int> ans(q);
    
    for(i = 0; i < sz(X); i++){
        graph[X[i]].pb(Y[i]);
        graph[Y[i]].pb(X[i]);
    }
    
    for(j = 0; j < q; j++){
        eq = vis = belong = cluster = can = can2 = vector <int> (n);
        for(i = 0; i < n; i++){
            if(i < L[j]) eq[i] = 0;
            else if(i > R[j]) eq[i] = 2;
            else eq[i] = 1;
        }
        
        clcnt = 0;
        
        for(i = 0; i < n; i++){
            if(!vis[i]){
                findcl(i);
                clcnt++;
            }
        }
        
        if(cluster[belong[S[j]]] == 0 || cluster[belong[E[j]]] == 2){
            continue;
        }
        for(i = 0; i < n; i++) vis[i] = 0;
        go(S[j], 0);
        for(i = 0; i < n; i++) vis[i] = 0;
        go(E[j], 2);
        
        for(i = 0; i < clcnt; i++){
            if(can[i] && can2[i]){
                ans[j] = 1;
                break;
            }
        }
    }
    
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Correct 5 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 777 ms 5624 KB Output is correct
11 Correct 609 ms 5504 KB Output is correct
12 Correct 347 ms 5504 KB Output is correct
13 Correct 805 ms 5624 KB Output is correct
14 Correct 634 ms 5504 KB Output is correct
15 Correct 727 ms 5752 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Correct 5 ms 4992 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 4 ms 5120 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 777 ms 5624 KB Output is correct
11 Correct 609 ms 5504 KB Output is correct
12 Correct 347 ms 5504 KB Output is correct
13 Correct 805 ms 5624 KB Output is correct
14 Correct 634 ms 5504 KB Output is correct
15 Correct 727 ms 5752 KB Output is correct
16 Execution timed out 4061 ms 35544 KB Time limit exceeded
17 Halted 0 ms 0 KB -