oj.uz

Submission #556082

# Submission time Handle Problem Language Result Execution time Memory
556082 2022-05-02T10:28:25 Z n0sk1ll Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 79412 KB 
#include "werewolf.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;

/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/







//Note to self: Check for overflow

vector<vector<int>> manji(200005),veci(200005);

int up[200005];
vector<int> redosled[200005];
int poc[200005],kraj[200005];
int gde[200005];

int Up(int x)
{
    if (up[x]<0) return x;
    return up[x]=Up(up[x]);
}

void dsu(int a, int b)
{
    a=Up(a),b=Up(b);
    if (a==b) return;
    if (up[a]<up[b]) swap(a,b);
    up[b]+=up[a],up[a]=b;
    for (auto it : redosled[a]) redosled[b].pb(it);
}

vector<pii> pom[200005];

int niz1[200005];
int l1[200005],r1[200005];

int niz2[200005];
int l2[200005],r2[200005];

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 m=X.size();
    int q=S.size();
    vector<int> ans(q,0);

    ff(i,0,m)
    {
        if (X[i]>Y[i]) swap(X[i],Y[i]);
        manji[Y[i]].pb(X[i]),veci[X[i]].pb(Y[i]);
    }

    ///wolf form

    ff(i,0,q) pom[i].clear();
    ff(i,0,q) pom[R[i]].pb({E[i],i});

    ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);

    ff(i,0,n)
    {
        for (auto it : manji[i]) dsu(i,it);
        for (auto it : pom[i])
        {
            poc[it.yy]=redosled[Up(it.xx)].front();
            kraj[it.yy]=redosled[Up(it.xx)].back();
        }
    }
    ff(i,0,n) niz1[i]=redosled[Up(0)][i];
    ff(i,0,n) gde[niz1[i]]=i;
    ff(i,0,q) l1[i]=gde[poc[i]],r1[i]=gde[kraj[i]];

    //ff(i,0,n) cout<<niz1[i]<<" "; cout<<endl;
    //ff(i,0,q) cout<<"["<<l1[i]<<","<<r1[i]<<"]"<<endl; cout<<endl;

    ///human form

    ff(i,0,q) pom[i].clear();
    ff(i,0,q) pom[L[i]].pb({S[i],i});

    ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);

    bff(i,0,n)
    {
        for (auto it : veci[i]) dsu(i,it);
        for (auto it : pom[i])
        {
            poc[it.yy]=redosled[Up(it.xx)].front();
            kraj[it.yy]=redosled[Up(it.xx)].back();
        }
    }
    ff(i,0,n) niz2[i]=redosled[Up(0)][i];
    ff(i,0,n) gde[niz2[i]]=i;
    ff(i,0,q) l2[i]=gde[poc[i]],r2[i]=gde[kraj[i]];

    //ff(i,0,n) cout<<niz2[i]<<" "; cout<<endl;
    //ff(i,0,q) cout<<"["<<l2[i]<<","<<r2[i]<<"]"<<endl; cout<<endl;

    ///intersect?

    ff(i,0,q)
    {
        set<int> prvi;
        fff(j,l1[i],r1[i]) prvi.insert(niz1[j]);
        fff(j,l2[i],r2[i]) if (prvi.count(niz2[j])) ans[i]=1;
    }

    return ans;
}

/*

6 6 3
5 1
1 2
1 3
3 4
0 3
2 5
4 2 1 2
4 2 2 2
5 4 3 4

6 6 21
5 1
1 2
1 3
3 4
0 3
2 5
0 0 0 0
0 0 1 1
0 0 2 2
0 0 3 3
0 0 4 4
0 0 5 5
1 1 1 1
1 1 2 2
1 1 3 3
1 1 4 4
1 1 5 5
2 2 2 2
2 2 3 3
2 2 4 4
2 2 5 5
3 3 3 3
3 3 4 4
3 3 5 5
4 4 4 4
4 4 5 5
5 5 5 5

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19096 KB Output is correct
2 Correct 11 ms 19120 KB Output is correct
3 Correct 13 ms 19156 KB Output is correct
4 Correct 10 ms 19116 KB Output is correct
5 Correct 11 ms 19124 KB Output is correct
6 Correct 14 ms 19156 KB Output is correct
7 Correct 12 ms 19180 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19096 KB Output is correct
2 Correct 11 ms 19120 KB Output is correct
3 Correct 13 ms 19156 KB Output is correct
4 Correct 10 ms 19116 KB Output is correct
5 Correct 11 ms 19124 KB Output is correct
6 Correct 14 ms 19156 KB Output is correct
7 Correct 12 ms 19180 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 605 ms 20024 KB Output is correct
11 Correct 444 ms 20052 KB Output is correct
12 Correct 35 ms 20088 KB Output is correct
13 Correct 736 ms 20044 KB Output is correct
14 Correct 638 ms 20056 KB Output is correct
15 Correct 417 ms 20052 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19096 KB Output is correct
2 Correct 11 ms 19120 KB Output is correct
3 Correct 13 ms 19156 KB Output is correct
4 Correct 10 ms 19116 KB Output is correct
5 Correct 11 ms 19124 KB Output is correct
6 Correct 14 ms 19156 KB Output is correct
7 Correct 12 ms 19180 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 12 ms 19156 KB Output is correct
10 Correct 605 ms 20024 KB Output is correct
11 Correct 444 ms 20052 KB Output is correct
12 Correct 35 ms 20088 KB Output is correct
13 Correct 736 ms 20044 KB Output is correct
14 Correct 638 ms 20056 KB Output is correct
15 Correct 417 ms 20052 KB Output is correct
16 Execution timed out 4083 ms 79412 KB Time limit exceeded
17 Halted 0 ms 0 KB -