Submission #556066

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556066	2022-05-02T10:08:13 Z	n0sk1ll	Werewolf (IOI18_werewolf)	C++14	0 / 100	4000 ms	86548 KB

werewolf

#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,n) pom[i].clear();
    ff(i,0,q) pom[R[i]].pb({S[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,n) 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,n) pom[i].clear();
    ff(i,0,q) pom[L[i]].pb({E[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,n) 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

*/

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:85:5: note: in expansion of macro 'ff'
   85 |     ff(i,0,m)
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:93:5: note: in expansion of macro 'ff'
   93 |     ff(i,0,n) pom[i].clear();
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:94:5: note: in expansion of macro 'ff'
   94 |     ff(i,0,q) pom[R[i]].pb({S[i],i});
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:96:5: note: in expansion of macro 'ff'
   96 |     ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:98:5: note: in expansion of macro 'ff'
   98 |     ff(i,0,n)
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:107:5: note: in expansion of macro 'ff'
  107 |     ff(i,0,n) niz1[i]=redosled[Up(0)][i];
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:108:5: note: in expansion of macro 'ff'
  108 |     ff(i,0,n) gde[niz1[i]]=i;
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:109:5: note: in expansion of macro 'ff'
  109 |     ff(i,0,n) l1[i]=gde[poc[i]],r1[i]=gde[kraj[i]];
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:116:5: note: in expansion of macro 'ff'
  116 |     ff(i,0,n) pom[i].clear();
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:117:5: note: in expansion of macro 'ff'
  117 |     ff(i,0,q) pom[L[i]].pb({E[i],i});
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,0,n) up[i]=-1,redosled[i].clear(),redosled[i].pb(i);
      |     ^~
werewolf.cpp:20:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   20 | #define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
      |                             ^
werewolf.cpp:121:5: note: in expansion of macro 'bff'
  121 |     bff(i,0,n)
      |     ^~~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:130:5: note: in expansion of macro 'ff'
  130 |     ff(i,0,n) niz2[i]=redosled[Up(0)][i];
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:131:5: note: in expansion of macro 'ff'
  131 |     ff(i,0,n) gde[niz2[i]]=i;
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:132:5: note: in expansion of macro 'ff'
  132 |     ff(i,0,n) l2[i]=gde[poc[i]],r2[i]=gde[kraj[i]];
      |     ^~
werewolf.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
werewolf.cpp:139:5: note: in expansion of macro 'ff'
  139 |     ff(i,0,q)
      |     ^~
werewolf.cpp:19:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
werewolf.cpp:142:9: note: in expansion of macro 'fff'
  142 |         fff(j,l1[i],r1[i]) prvi.insert(niz1[j]);
      |         ^~~
werewolf.cpp:19:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
werewolf.cpp:143:9: note: in expansion of macro 'fff'
  143 |         fff(j,l2[i],r2[i]) if (prvi.count(niz2[j])) ans[i]=1;
      |         ^~~

Subtask #1

0 / 7.0

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

Subtask #2

0 / 8.0

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

Subtask #3

0 / 34.0

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

Subtask #4

0 / 51.0

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