제출 #90379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90379		Bodo171	Birthday gift (IZhO18_treearray)	C++14	0 / 100	24 ms	23928 KiB

treearray

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
set<int> s[nmax],og[nmax];
int l[nmax],r[nmax],seq[nmax];
int tt[20][nmax];
int n,m,q,i,j,poz,val,nr,a,b,tip,x,ll,rr;
void dfs(int x)
{
    l[x]=++nr;
    for(int i=0;i<v[x].size();i++)
        if(!l[v[x][i]])
    {
        tt[0][v[x][i]]=x;
        dfs(v[x][i]);
    }
    r[x]=nr;
}
bool cup(int x,int y)
{
    return (l[x]<=l[y]&&l[y]<=r[x]);
}
int lca(int a,int b)
{
    for(int p=17;p>=0;p--)
        if(tt[p][a]&&(!cup(tt[p][a],b)))
          a=tt[p][a];
    if(!cup(a,b))
         a=tt[0][a];
    return a;
}
void prc()
{
    for(i=1;i<=17;i++)
        for(j=1;j<=n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
}
int main()
{
    freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    prc();
    for(i=1;i<=n;i++)
        s[i].insert(m+1),og[i].insert(m+1);
    for(i=1;i<=m;i++)
    {
        cin>>seq[i];
        og[seq[i]].insert(i);
    }
    for(i=1;i<m;i++)
    {
        s[lca(seq[i],seq[i+1])].insert(i);
    }
    for(i=1;i<=q;i++)
    {
        cin>>tip;
        if(tip==1)
        {
            cin>>poz>>val;
            if(poz>1) s[lca(seq[poz-1],seq[poz])].erase(poz-1);
            if(poz<m) s[lca(seq[poz],seq[poz+1])].erase(poz);
            og[seq[poz]].erase(poz);
            seq[poz]=val;
            if(poz>1) s[lca(seq[poz-1],seq[poz])].insert(poz-1);
            if(poz<m) s[lca(seq[poz],seq[poz+1])].insert(poz);
            og[seq[poz]].insert(poz);
        }
        else
        {
            cin>>ll>>rr>>x;
            poz=(*s[x].lower_bound(ll));
            if(poz<rr) cout<<poz<<' '<<poz+1<<'\n';
            else
            {
                poz=(*og[x].lower_bound(ll));
                if(poz<=rr) cout<<poz<<' '<<poz<<'\n';
                else cout<<"-1 -1\n";
            }
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

treearray.cpp: In function 'void dfs(int)':
treearray.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
treearray.cpp: In function 'int main()':
treearray.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("data.in","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44