이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
bool vis[N];
int Lx , Rx;
vector<int> adj[N];
vector<int> v;
int nx ;
int pos[N];
void solve(int x ){
v.push_back(x);
vis[x] = true;
for(auto w : adj[x]){
if(!vis[w]){
solve(w);
}
}
}
struct node{
int minvl , maxvl;
} st[4*N];
node merge(node a , node b){
node x;
x.minvl = min(a.minvl , b.minvl);
x.maxvl = max(a.maxvl , b.maxvl);
return x;
}
void build(int l = 0 , int r = nx - 1 , int curr = 1){
// cout<<l<<" " <<r <<" " << curr << endl;
int mid = (l+r)/2;
if(l == r){
st[curr].minvl = st[curr].maxvl = v[l];
return ;
}
build(l , mid , 2*curr);
build(mid + 1 , r , 2*curr + 1);
st[curr] = merge(st[2*curr] , st[2*curr + 1]);
}
node query(int x , int y , int l = 0 , int r = nx -1 , int curr = 1){
int mid = (l+r)/2;
if(l == x && r == y){
return st[curr];
}
if(y <= mid){
return query(x,y,l,mid,2*curr);
}
else if(x > mid){
return query(x,y,mid+1 , r , 2*curr +1);
}
else{
return merge(query(x,mid,l,mid,2*curr) , query(mid + 1 , y , mid + 1 , r , 2*curr + 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) {
nx = N ;
for(int i = 0 ; i < X.size() ; i ++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for(int i = 0 ; i < N ; i ++){
if(adj[i].size() == 1){
solve(i);
break;
}
}
for(int i = 0 ; i < N ; i ++){
pos[v[i]] = i;
}
build();
int Q = S.size();
std::vector<int> A(Q, 0);
for(int i = 0; i < Q; ++i) {
if(pos[S[i]] < pos[E[i]]){
int l = pos[S[i]] , r = pos[E[i]];
int ansj = l;
while(l<=r){
int mid = (l+r)/2;
if(query(pos[S[i]] , mid).minvl < L[i]){
r = mid - 1;
}
else{
l = mid + 1;
ansj = mid;
}
}
l = pos[S[i]] , r = pos[E[i]];
int ansj2 = r;
while(l<=r){
int mid = (l+r)/2;
if(query(mid , pos[E[i]]).maxvl > R[i]){
l = mid + 1;
}
else{
r = mid - 1;
ansj2 = mid;
}
}
if(ansj >= ansj2){
A[i] = 1;
}
}
else{
int l = pos[E[i]] , r = pos[S[i]];
int ansj = l;
while(l<=r){
int mid = (l+r)/2;
if(query(pos[E[i]] , mid).maxvl > R[i]){
r = mid - 1;
}
else{
l = mid + 1;
ansj = mid;
}
}
l = pos[E[i]] , r = pos[S[i]];
int ansj2 = r;
while(l<=r){
int mid = (l+r)/2;
if(query(mid , pos[S[i]]).minvl < L[i]){
l = mid + 1;
}
else{
r = mid - 1;
ansj2 = mid;
}
}
if(ansj >= ansj2){
A[i] = 1;
}
}
}
return A;
}
컴파일 시 표준 에러 (stderr) 메시지
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:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < X.size() ; i ++){
~~^~~~~~~~~~
# | 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... |