이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
#define cout if(false) cout
struct dsu{
vector<int> par;
int sz;
dsu(int size){
sz = size;
par = vector<int>(sz, -1);
}
int find(int cur){
if(par[cur] == -1) return cur;
return par[cur] = find(par[cur]);
}
bool merge(int a, int b){
a = find(a);
b = find(b);
if(a == b) return false;
par[a] = b;
return true;
}
};
vector<vector<int> > g;
int tym = 0;
void eulerTour(int cur, vector<vector<int> >&G, vector<int>& arr, vector<int>& sl, vector<int>& el){
tym++;
sl[cur] = tym;
arr.push_back(cur);
for(int u: G[cur]){
eulerTour(u, G, arr, sl, el);
}
el[cur] = tym;
}
struct bit{
vector<int> t;
int sz;
bit(int size){
sz = size;
t = vector<int>(sz+1, 0);
}
int query(int i){
i++;
cout<<"Q: "<<i<<endl;
assert(i > 0 && i <= sz);
int ret = 0;
for(; i > 0; i -= i&(-i)){
ret += t[i];
}
return ret;
}
int query(int l, int r){
return query(r) - (l==0?0:query(l-1));
}
void upd(int i, int val){
i++;
for(; i <= sz; i += i&(-i)){
t[i] += val;
}
}
};
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 Q = S.size();
int m = x.size();
g.resize(n);
for(int i = 0; i < m; i++){
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
cout<<"REACHED HERE"<<endl;
//doing this for L
vector<int> lpar(Q);
vector<int> eulerLeft, startL(n), endL(n);
{
vector<vector<int> > eventL(n);
for(int i = 0; i < Q; i++){
eventL[L[i]].push_back(i);
}
vector<vector<int> > gl(n);
dsu dl(n);
for(int i = n-1; i >= 0; i--){
//add node i
for(int u: g[i]){
if(u < i) continue;
int par= dl.find(u);
if(par == i) continue;
gl[i].push_back(par);
dl.merge(par, i);
}
//node added, now find parents for all those
for(int u: eventL[i]){
int p = dl.find(S[u]);
lpar[u] = p;
}
}
cout<<"GRAPH HERE"<<endl;
// for(int i = 0; i < n; i++){
// cout<<i<<" : ";
// for(int u: gl[i]){
// cout<<u<<" ";
// }
// cout<<endl;
// }
tym = -1;
eulerTour(0, gl, eulerLeft, startL, endL);
assert(eulerLeft.size() == n);
}
cout<<"REACHED HERE"<<endl;
//doing this for R
vector<int> rpar(Q);
vector<int> eulerRight, startR(n), endR(n);
{
vector<vector<int> > eventR(n);
for(int i = 0; i < Q; i++){
eventR[R[i]].push_back(i);
}
vector<vector<int> > gl(n);
dsu dl(n);
for(int i = 0; i < n; i++){
//add node i
for(int u: g[i]){
if(u > i) continue;
int par= dl.find(u);
if(par == i) continue;
gl[i].push_back(par);
dl.merge(par, i);
}
//node added, now find parents for all those
for(int u: eventR[i]){
int p = dl.find(E[u]);
rpar[u] = p;
}
}
cout<<"GRAPH HERE"<<endl;
// for(int i = 0; i < n; i++){
// cout<<i<<" : ";
// for(int u: gl[i]){
// cout<<u<<" ";
// }
// cout<<endl;
// }
tym = -1;
eulerTour(n-1, gl, eulerRight, startR, endR);
assert(eulerRight.size() == n); }
//found euler tour array for both. need to check for intersection for each query
//find inverse permutation now
cout<<"REACHED HERE"<<endl;
cout<<"EULER TOUR"<<endl;
for(int i = 0; i < n; i++){
cout<<eulerLeft[i]<<" ";
assert(eulerLeft[i] < n && eulerLeft[i] >= 0);
}
cout<<endl;
for(int i = 0; i < n; i++){
cout<<eulerRight[i]<<" ";
assert(eulerRight[i] < n && eulerRight[i] >= 0);
}
cout<<endl;
vector<int> rev(n);
for(int i = 0; i < n; i++){
assert(rev[eulerRight[i]] == 0);
rev[eulerRight[i]] = i;
}
vector<int> arr(n);
for(int i = 0; i < n; i++){
arr[i] = rev[eulerLeft[i]];
assert(arr[i] >= 0 && arr[i] < n);
}
//now arr is the one we care about
//need to check whether in box there is atleast one
cout<<"DONE ALL "<<endl;
vector<vector<int> > events(n);
for(int i = 0; i < Q; i++){
cout<<i<<" "<<lpar[i]<<" "<<startL[lpar[i]]<<" "<<endL[lpar[i]]<<endl;
if(startL[lpar[i]]-1 >= 0) events[startL[lpar[i]]-1].push_back(i);
events[endL[lpar[i]]].push_back(i);
assert(endL[lpar[i]] < n && endL[lpar[i]] >= 0);
}
cout<<"REACHED HERE"<<endl;
vector<int> ans(Q);
bit b(n);
// for(int i = 0; i < n; i++){
// b.upd(arr[i], 1);
// for(int u: events[i]){
// assert(endR[rpar[u]] < n && endR[rpar[u]] >= 0);
// cout<<"RPAR "<<u<<" "<<rpar[u]<<" "<<startR[rpar[u]]<<endl;
// if(endL[lpar[u]] == i){ //exiting
// ans[u] += b.query(startR[rpar[u]], endR[rpar[u]]);
// }else{
// ans[u] -= b.query(startR[rpar[u]], endR[rpar[u]]);
// }
// }
// }
for(int i = 0; i < Q; i++){
for(int l = startL[lpar[i]]; l <= endL[lpar[i]]; l++){
if(arr[l] >= startR[rpar[i]] && arr[l] <= endR[rpar[i]]){
ans[i]++;
}
}
}
cout<<"REACHED HERE"<<endl;
for(int i = 0; i < n; i++){
assert(ans[i] >= 0);
ans[i] = ans[i] > 0;
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from werewolf.cpp:2:
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:124:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(eulerLeft.size() == n);
~~~~~~~~~~~~~~~~~^~~~
werewolf.cpp:166:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(eulerRight.size() == n); }
~~~~~~~~~~~~~~~~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |