제출 #530481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530481		azberjibiou	Inside information (BOI21_servers)	C++17	100 / 100	544 ms	65232 KiB

servers

#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++)
      |                     ~~~^~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5