이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=120005;
const int mxM=1010;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1e15;
const ll P1=1000000007;
const ll P2=1000000009;
typedef struct query{
char typ;
int s, e;
}edge;
int N, K;
vector <pii> vadj[mxN], eadj[mxN];
vector <int> echild[mxN];
query Q[2*mxN];
int vpar[mxN], vsps[20][mxN], vdep[mxN];
int edep[mxN], cursum[mxN], esps[20][mxN];
int g[mxN];
int sub[mxN];
int in[mxN], out[mxN], eidx;
int ntime;
void dfsv0(int now, int pre)
{
for(pii ele : vadj[now]) if(ele.fir!=pre)
{
vdep[ele.fir]=vdep[now]+1;
vpar[ele.fir]=ele.sec;
vsps[0][ele.fir]=now;
dfsv0(ele.fir, now);
}
}
void dfse0(int now, int pre)
{
sub[now]=1;
for(pii ele : eadj[now]) if(ele.fir!=pre)
{
echild[now].push_back(ele.fir);
esps[0][ele.fir]=now;
edep[ele.fir]=edep[now]+1;
cursum[ele.fir]+=cursum[now]+ele.sec;
dfse0(ele.fir, now);
sub[now]+=sub[ele.fir];
}
for(int i=1;i<echild[now].size();i++)
{
if(sub[echild[now][0]]<sub[echild[now][i]]) swap(echild[now][0], echild[now][i]);
}
}
void dfse1(int now)
{
in[now]=++eidx;
if(echild[now].empty()) return;
g[echild[now][0]]=g[now];
for(int i=1;i<echild[now].size();i++) g[echild[now][i]]=echild[now][i];
for(int ele : echild[now]) dfse1(ele);
out[now]=eidx;
}
void solvN1()
{
for(int i=0;i<N+K;i++)
{
if(Q[i].typ=='C') cout << 1 << '\n';
if(Q[i].typ=='Q') cout << "yes" << '\n';
}
}
int solv_lca(int a, int b, int sps[][mxN], int *dep)
{
if(dep[a]<dep[b]) swap(a, b);
for(int i=19;i>=0;i--)
{
if(dep[a]>=dep[b]+(1<<i)) a=sps[i][a];
}
if(a==b) return a;
for(int i=19;i>=0;i--) if(sps[i][a]!=sps[i][b]) a=sps[i][a], b=sps[i][b];
return sps[0][a];
}
int vdown_edge(int s, int e)
{
for(int i=19;i>=0;i--) if(vdep[s]>vdep[e]+(1<<i)) s=vsps[i][s];
return s;
}
ll seg[4*mxN], lazy[4*mxN];
void propagate(int idx, int s, int e)
{
int mid=(s+e)/2;
seg[2*idx]+=(mid-s+1)*lazy[idx];
seg[2*idx+1]+=(e-mid)*lazy[idx];
lazy[2*idx]+=lazy[idx];
lazy[2*idx+1]+=lazy[idx];
lazy[idx]=0;
}
void seg_upd(int idx, int s1, int e1, int s2, int e2)
{
if(s1>e2 || s2>e1) return;
if(s2<=s1 && e1<=e2)
{
seg[idx]+=e1-s1+1;
lazy[idx]++;
return;
}
propagate(idx, s1, e1);
int mid=(s1+e1)/2;
seg_upd(2*idx, s1, mid, s2, e2);
seg_upd(2*idx+1, mid+1, e1, s2, e2);
seg[idx]=seg[2*idx]+seg[2*idx+1];
}
int seg_solv(int idx, int s1, int e1, int s2, int e2)
{
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2) return seg[idx];
propagate(idx, s1, e1);
int mid=(s1+e1)/2;
return seg_solv(2*idx, s1, mid, s2, e2)+seg_solv(2*idx+1, mid+1, e1, s2, e2);
}
void hld_upd(int s, int e)
{
while(edep[g[s]]>edep[e])
{
seg_upd(1, 1, N-1, in[g[s]], in[s]);
s=esps[0][g[s]];
}
seg_upd(1, 1, N-1, in[e], in[s]);
}
int hld_solv(int s, int e)
{
int ret=0;
while(edep[g[s]]>edep[e])
{
ret+=seg_solv(1, 1, N-1, in[g[s]], in[s]);
s=esps[0][g[s]];
}
ret+=seg_solv(1, 1, N-1, in[e], in[s]);
return ret;
}
int solvC(int now)
{
int enow=vadj[now][0].sec;
int npar=enow;
for(int i=19;i>=0;i--)
{
if(esps[i][npar]!=0 && cursum[esps[i][npar]]==cursum[enow]) npar=esps[i][npar];
}
return hld_solv(enow, npar);
}
bool esolvQ(int now, int data)
{
//printf("now=%d, data=%d\n", now, data);
//printf("ntime=%d\n", ntime);
if(now==data) return (now<=ntime);
int elca=solv_lca(now, data, esps, edep);
return (cursum[data]==cursum[elca] && cursum[elca]-cursum[now]==edep[elca]-edep[now] && now<=ntime);
}
bool solvQ(int now, int data)
{
if(now==data) return true;
int vlca=solv_lca(now, data, vsps, vdep);
if(vlca==now)
{
return esolvQ(vpar[vdown_edge(data, now)], vpar[data]);
}
else if(vlca==data)
{
return esolvQ(vpar[now], vpar[vdown_edge(now, data)]);
}
else
{
return esolvQ(vpar[now], vpar[data]);
}
}
void eupd(int now)
{
int npar=now;
for(int i=19;i>=0;i--)
{
if(esps[i][npar]!=0 && cursum[esps[i][npar]]-cursum[npar]==edep[esps[i][npar]]-edep[npar]) npar=esps[i][npar];
}
hld_upd(now, npar);
}
int main()
{
gibon
cin >> N >> K;
int idx=1;
for(int i=0;i<N+K-1;i++)
{
cin >> Q[i].typ;
if(Q[i].typ=='C') cin >> Q[i].s;
else cin >> Q[i].s >> Q[i].e;
if(Q[i].typ=='S')
{
vadj[Q[i].s].emplace_back(Q[i].e, idx);
vadj[Q[i].e].emplace_back(Q[i].s, idx);
idx++;
}
}
if(N==1)
{
solvN1();
return 0;
}
for(int i=1;i<=N;i++)
{
if(vadj[i].size())
sort(vadj[i].begin(), vadj[i].end(), [](pii a, pii b){return a.sec<b.sec;});
for(int j=0;j+1<vadj[i].size();j++)
{
eadj[vadj[i][j].sec].emplace_back(vadj[i][j+1].sec, 1);
eadj[vadj[i][j+1].sec].emplace_back(vadj[i][j].sec, 0);
}
}
dfsv0(1, -1);
for(int i=1;i<20;i++) for(int j=1;j<=N;j++) vsps[i][j]=vsps[i-1][vsps[i-1][j]];
g[1]=1;
dfse0(1, -1);
dfse1(1);
for(int i=1;i<20;i++) for(int j=1;j<=N;j++) esps[i][j]=esps[i-1][esps[i-1][j]];
/*for(int i=1;i<N;i++)
{
printf("i=%d: ", i);
for(auto ele : eadj[i]) printf("(%d, %d) ", ele.fir, ele.sec);
printf("\n");
}
for(int i=1;i<N;i++) printf("in[%d]=%d\n", i, in[i]);
for(int i=1;i<N;i++) printf("g[%d]=%d\n", i, g[i]);*/
for(int i=0;i<N+K-1;i++)
{
if(Q[i].typ=='S')
{
ntime++;
eupd(ntime);
}
if(Q[i].typ=='C')
{
cout << solvC(Q[i].s)+1 << '\n';
}
if(Q[i].typ=='Q')
{
cout << (solvQ(Q[i].s, Q[i].e) ? "yes" : "no") << '\n';
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In function 'void dfse0(int, int)':
servers.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i=1;i<echild[now].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'void dfse1(int)':
servers.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=1;i<echild[now].size();i++) g[echild[now][i]]=echild[now][i];
| ~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:217:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for(int j=0;j+1<vadj[i].size();j++)
| ~~~^~~~~~~~~~~~~~~
# | 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... |
# | 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... |
# | 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... |