이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define dl double long
const int maxn = 200200;
int n,m,q;
vector < int > ans;
int p1[maxn];
int s1[maxn];
vector < int > v[maxn],s,e,l,r;
vector < pair < int* , int > > bl;
vector < pair < int , int > > ask[maxn];
int get1( int x )
{
return (p1[x] == x ? x : get1(p1[x]));
}
void roll( int i )
{
while( (int)bl.size() > i ){
*bl.back().fi = bl.back().se;
bl.pop_back();
}
}
void meg1( int x , int y )
{
int px = get1( x );
int py = get1( y );
if( px == py )return;
if( s1[px] < s1[py] ){
swap( px , py );
}
bl.push_back({ &p1[py] , p1[py] });
bl.push_back({ &s1[px] , s1[px] });
p1[py] = px;
s1[px] += s1[py];
}
void solve( int l , int r )
{
if( l > r )return;
int m = (l + r) / 2;
int l3 = (int)bl.size();
for( int i = l; i <= m; i++ ){
for( auto x : v[i] ){
if( x > m )continue;
meg1( i , x );
}
}
int l1 = (int)bl.size();
for( int i = m + 1; i <= r; i++ ){
for( auto x : v[i] ){
if( x <= m )continue;
meg1( i , x );
}
}
int l2 = (int)bl.size();
for( int i = m; i >= l; i-- ){
for( auto x : v[i] ){
if( x <= m )continue;
meg1( i , x );
}
for( auto x : ask[i] ){
if( x.fi < m )continue;
int x1 = get1( e[x.se] );
int x2 = get1( s[x.se] );
ans[x.se] = (x1 == x2);
}
}
roll( l1 );
solve( m + 1 , r );
roll( l3 );
l1 = (int)bl.size();
for( int i = m + 1; i <= r; i++ ){
for( auto x : v[i] ){
if( x <= m )continue;
meg1( i , x );
}
}
solve( l , m - 1 );
roll( l1 );
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
m = (int)X.size();
q = (int)L.size();
for( int i = 0; i < m; i++ ){
int x = X[i] , y = Y[i];
v[x].push_back(y);
v[y].push_back(x);
}
for( int i = 0; i < q; i++ ){
ask[L[i]].push_back({ R[i] , i });
}
for( int i = 0; i < maxn; i++ ){
p1[i] = i;
s1[i] = 1;
}
ans.resize(q);
s = S;
e = E;
l = L;
r = R;
//solve( 0 , n - 1 );
for( int i = 0; i < q; i++ ){
roll( 0 );
for( int j = 0; j <= R[i]; j++ ){
for( auto x : v[j] ){
if( x > R[i] )continue;
meg1( j , x );
}
}
for( int j = L[i]; j < n; j++ ){
for( auto x : v[j] ){
if( x < L[i] )continue;
meg1( j , x );
}
}
ans[i] = (get1(S[i]) == get1(E[i]));
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
werewolf.cpp: In function 'void solve(int, int)':
werewolf.cpp:66:9: warning: unused variable 'l2' [-Wunused-variable]
66 | int l2 = (int)bl.size();
| ^~
# | 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... |