oj.uz

답안 #90378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90378 2018-12-21T12:23:07 Z Bodo171 Birthday gift (IZhO18_treearray) C++14
0 / 100
 20 ms 24060 KB 
#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(seq[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;
}

Compilation message

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

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23928 KB n=5
2 Incorrect 20 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23928 KB n=5
2 Incorrect 20 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23928 KB n=5
2 Incorrect 20 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23928 KB n=5
2 Incorrect 20 ms 24060 KB Wrong range.
3 Halted 0 ms 0 KB -