이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adjlist;
int n,m,q;
struct UFDS{
vector<int> parent;
vector<vector<int>> adjlist;
vector<int> eulertour;
UFDS(int n){
parent.resize(n);
adjlist.resize(n);
for (int i = 0; i<n; i++){
parent[i]=i;
}
}
int root(int x){
if (parent[x]==x){
return x;
}
return root(parent[x]);
}
void connect(int a, int b){
//cout<<"connect "<<a<<' '<<b<<endl;
// connect b to a
int rb = root(b);
if (rb==a){return;}
parent[rb]=a;
adjlist[a].push_back(rb);
}
void geneulertour(int node){
//cout<<"gen "<<node<<endl;
eulertour.push_back(node);
for (int i : adjlist[node]){
geneulertour(i);
eulertour.push_back(node);
}
if (adjlist[node].size()==0){
eulertour.push_back(node);
}
}
};
void getranges(vector<int> &seq, bool increasing, vector<int> &queries,
vector<int> &limits, vector<int> &lvals, vector<int> &rvals){
vector<vector<int>> val2ind(n);
for (int i = 0; i<seq.size(); i++){
val2ind[seq[i]].push_back(i);
}
vector<int> inds(q);
for (int i = 0; i<q; i++){
inds[i]=i;
}
if (increasing){
sort(inds.begin(),inds.end(),[&limits](int a, int b){return limits[a]<limits[b];});
} else {
sort(inds.begin(),inds.end(),[&limits](int a, int b){return limits[a]>limits[b];});
}
set<int> insertedpoints;
insertedpoints.insert(-1);
insertedpoints.insert(seq.size());
int prevval = increasing?0:n-1;
for (int i = 0; i<q; i++){
//cout<<"limit: "<<limits[inds[i]]<<'\n';
while (prevval!=limits[inds[i]]){
for (int v : val2ind[prevval]){
//cout<<"insert "<<v<<'\n';
insertedpoints.insert(v);
}
prevval+=increasing?1:-1;
}
auto lb = insertedpoints.lower_bound(val2ind[queries[inds[i]]][0]);
//cout<<"lower: "<<*lb<<'\n';
//cout<<"prev: "<<*(prev(lb))<<'\n';
lvals[inds[i]]=*(prev(lb))+1;
rvals[inds[i]]=*lb-1;
//cout<<inds[i]<<'\n';
//cout<<lvals[inds[i]]<<' '<<rvals[inds[i]]<<'\n';
}
}
void display(vector<int> &v){
for (int i : v){
cout<<i<<' ';
}cout<<'\n';
}
struct FenwickTree{
vector<int> fenwick;
int n;
FenwickTree(int _n){
n=_n;
//fenwick.resize(n+1);
}
void update(int ind){
//cout<<"update "<<ind<<'\n';
ind++;
while (ind<=n){
fenwick[ind]++;
ind+=ind&(-ind);
}
}
int qsum(int ind){
ind++;
if (ind==0){return 0;}
int ans = 0;
while (ind>0){
ans+=fenwick[ind];
ind-=ind&(-ind);
}
return ans;
}
int query(int a, int b){
//cout<<"query "<<a<<' '<<b<<'\n';
return qsum(b)-qsum(a-1);
}
};
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) {
n=N;
m=x.size();
q=S.size();
adjlist.resize(n);
for (int i = 0; i<m; i++){
adjlist[x[i]].push_back(y[i]);
adjlist[y[i]].push_back(x[i]);
}
UFDS ue(n);
for (int i = 1; i<n; i++){
for (int j : adjlist[i]){
if (j>i){continue;}
ue.connect(i,j);
}
}
ue.geneulertour(n-1);
UFDS us(n);
for (int i = n-2; i>=0; i--){
for (int j : adjlist[i]){
if (j<i){continue;}
us.connect(i,j);
}
}
us.geneulertour(0);
//display(us.eulertour);
//display(ue.eulertour);
vector<int> sl(q), sr(q), el(q), er(q);
getranges(us.eulertour, true, S, L, sl, sr);
getranges(ue.eulertour, false, E, R, el, er);
//display(sl);display(sr);
//display(el);display(er);
// s - x axis, e - y axis
vector<pair<int,int>> coords;
vector<vector<int>> yval2coord(n);
for (int i = 0; i<ue.eulertour.size(); i++){
yval2coord[ue.eulertour[i]].push_back(i);
}
for (int i = 0; i<us.eulertour.size(); i++){
/*for (int y : yval2coord[us.eulertour[i]]){
//cout<<i<<' '<<y<<'\n';
coords.push_back({i,y});
}*/
coords.push_back({i,yval2coord[us.eulertour[i]][0]});
}
vector<pair<int,int>> rangequeries;
vector<int> qans(2*q);
for (int i = 0; i<q; i++){
rangequeries.push_back({sl[i]-1,2*i});
rangequeries.push_back({sr[i],2*i+1});
}
FenwickTree ft(ue.eulertour.size());
sort(rangequeries.begin(),rangequeries.end());
int ind = 0;
for (int i = 0; i<2*q; i++){
//cout<<"query: "<<rangequeries[i].first<<' '<<rangequeries[i].second<<'\n';
//cout<<"for: "<<rangequeries[i].second/2<<'\n';
if (rangequeries[i].first==-1){
qans[rangequeries[i].second]=0;
continue;
}
while (ind<coords.size()&&coords[ind].first<=rangequeries[i].first){
ft.update(coords[ind].second);
ind++;
}
int yrange = rangequeries[i].second/2;
qans[rangequeries[i].second]=ft.query(el[yrange],er[yrange]);
//cout<<qans[rangequeries[i].second]<<'\n';
}
vector<int> ans(q,0);
for (int i = 0; i<q; i++){
//cout<<"query "<<i<<endl;
//cout<<qans[2*i+1]<<' '<<qans[2*i]<<'\n';
if (qans[2*i+1]-qans[2*i]>0){
ans[i]=1;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
werewolf.cpp: In function 'void getranges(std::vector<int>&, bool, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
werewolf.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i<seq.size(); i++){
| ~^~~~~~~~~~~
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:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for (int i = 0; i<ue.eulertour.size(); i++){
| ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for (int i = 0; i<us.eulertour.size(); i++){
| ~^~~~~~~~~~~~~~~~~~~~
werewolf.cpp:207:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | while (ind<coords.size()&&coords[ind].first<=rangequeries[i].first){
| ~~~^~~~~~~~~~~~~~
# | 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... |