oj.uz

답안 #1004818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004818 2024-06-21T16:59:46 Z modwwe Tourism (JOI23_tourism) C++17
0 / 100
 5000 ms 23532 KB 
///https://www.instagram.com/_modwwe/
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e18;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    int a,b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c, d,e,f;

};
int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l;
int  i,s10,s12;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
  //  fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo();
}
ic t[400007];
int depth[100007];
ic a[100007];
int c[100007];
ib euler[100007];
int d[100007];
int st[17][100007];
int ans[1000007];
int S;
int b[100007];
vector<int> v[100007];
int e[100007];
int lz[400007];
bool cmp(ic a,ic b)
{
    if(a.a/S==b.a/S) return a.b<b.b;
    return        a.a/S<b.a/S;
}
void build(int node,int l,int r)
{
    t[node].b= n+1;
    if(l==r)return;
    int mid=l+r>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
}

void upd(int node,int l,int r,int l1,int r1,int cc)
{
    if(l>r1||r<l1) return;
    if(l>=l1&&r<=r1)
    {
        t[node].c+=cc;
        if(t[node].c>0) t[node]= {l,r,t[node].c};
        else t[node]= {0,n+1,0};
        return;
    }
    int mid=l+r>>1;
    upd(node<<1,l,mid,l1,r1,cc);
    upd(node<<1|1,mid+1,r,l1,r1,cc);
    t[node].a=max(t[node<<1].a,t[node<<1|1].a);
    t[node].b=min(t[node<<1].b,t[node<<1|1].b);
}
int get1(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1) return t[node].a;

    int mid=l+r>>1;
    return max(get1(node<<1,l,mid,l1,r1),get1(node<<1|1,mid+1,r,l1,r1));
}
int get2(int node, int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return n+1;
    if(l>=l1&&r<=r1) return t[node].b;
    int mid=l+r>>1;
    return min(get2(node<<1,l,mid,l1,r1),get2(node<<1|1,mid+1,r,l1,r1));
}
void dfs(int x,int y)
{
    st[0][x]=y;
    depth[x]=depth[y]+1;
    euler[x].a=++dem;
    c[dem]=x;
    for(auto f:v[x])
        if(f!=y)
            dfs(f,x);
    euler[x].b=dem;
}
int lca(int x,int y,int cc)
{
    if(x==0||x==n+1||y==0||y==n+1) return 1;
    if(depth[x]<depth[y]) swap(x,y),cc=0;
    int ss=depth[x]-depth[y]-1;
    if(ss>=0)
        for(int j=0; j<17; j++)
            if(bit(ss,j))
                x=st[j][x];
    if(st[0][x]==y) return x;
    if(ss!=-1)  x=st[0][x];
    for(int j=16; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    if(cc==0) return y;
    else
        return x;
}
int lca2(int x,int y)
{
    if(x==0 )return y;
    if(y==0 )return x;
    if(depth[x]<depth[y]) swap(x,y);
    int ss=depth[x]-depth[y];
    for(int j=0; j<17; j++)
        if(bit(ss,j))
            x=st[j][x];
    if(x==y) return x;
    for(int j=16; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    return st[0][x];
}
void build2(int node,int l,int r)
{
    if(l==r)
    {
        lz[node]=b[l];
        return;
    }
    int mid=l+r>>1;
    build2(node<<1,l,mid);
    build2(node<<1|1,mid+1,r);
    lz[node]=lca2(lz[node<<1],lz[node<<1|1]);
}
int get_lca(int node,int l,int r,int l1,int r1)
{
    if(l>r1||r<l1) return 0;
    if(l>=l1&&r<=r1) return lz[node];
    int mid=l+r>>1;
    return lca2(get_lca(node<<1,l,mid,l1,r1),get_lca(node<<1|1,mid+1,r,l1,r1));
}
void add(int x)
{
    s2=get1(1,1,n,1,euler[x].a);
    s3=get2(1,1,n,euler[x].a,n);
    upd(1,1,n,euler[x].a,euler[x].a,1);
    s2=c[s2];
    s3=c[s3];
    if(s2==x||s3==x) return;
    s2=lca(x,s2,1);
    s3=lca(x,s3,1);
    if(depth[s2]<depth[s3]) swap(s2,s3);
    if(depth[x]>=depth[s2])
    {
        s4+=depth[x]-depth[s2]+1;
        d[x]=s2;
        e[s2]=x;
    }
}
void del(int x)
{
    upd(1,1,n,euler[x].a,euler[x].a,-1);
    s5=d[x];
    if(d[x]==0) return;
    s2=get1(1,1,n,euler[s5].a,euler[x].a);
    s3=get2(1,1,n,euler[x].a,euler[s5].b);
    s2=c[s2];
    s3=c[s3];
    if(s2==x||s3==x) return;
    s4-=(depth[x]-depth[s5]+1);
    if(s2==0&&s3==0) return;
    e[s5]=0;
    d[x]=0;
    s9=s2;
    s2=lca(s2,x,1);
    s3=lca(s3,x,1);
    if(st[0][s2]==s9&&depth[s2]>=depth[s3]&&d[s2]==0)
    {
        s2=s9;
        s4+=depth[s2]-depth[s5]+1;
        d[s2]=s5;
        e[s5]=s2;
        return;
    }
    if(depth[s2]<depth[s3])swap(s2,s3);
    if(depth[s5]<depth[s2])
    {
        s3=e[s2];
        e[s2]=0;
        e[s5]=s3;
        d[s3]=s5;
        s4+=(depth[s2]-depth[s5]);
    }
}
void del2(int x)
{
    upd(1,1,n,euler[x].a,euler[x].a,-1);
    s5=d[x];
    if(d[x]==0) return;
    s2=get1(1,1,n,euler[s5].a,euler[x].a);
    s3=get2(1,1,n,euler[x].a,euler[s5].b);
    s2=c[s2];
    s3=c[s3];
    if(s2==x||s3==x) return;
    s4-=(depth[x]-depth[s5]+1);
    if(s2==0&&s3==0) return;
    e[s5]=0;
    d[x]=0;
    s9=s2;
    s2=lca(s2,x,1);
    s3=lca(s3,x,1);
    if(st[0][s2]==s9&&depth[s2]>=depth[s3]&&d[s2]==0)
    {
        s2=s9;
        s4+=depth[s2]-depth[s5]+1;
        d[s2]=s5;
        e[s5]=s2;
        return;
    }
    if(depth[s2]<depth[s3])swap(s2,s3);
    if(depth[s5]<depth[s2])
    {
        s3=e[s2];
        e[s2]=0;
        e[s5]=s3;
        d[s3]=s5;
        s4+=(depth[s2]-depth[s5]);
    }
}
void go(int x,int y)
{
    while(r<y)
    {
        r++;
        add(b[r]);
    }
    while(l>x)
    {
        l--;
        add(b[l]);
    }
    while(l<x)
    {
        del(b[l]);
        //   cout<<l<<" "<<s4,down
        l++;
    }
    while(r>y)
    {
        del(b[r]);
        r--;
    }
}
void phongbeo()
{
    cin>>n>>m>>k;
    S=400;
    for(int i=1; i<n; i++)
        cin>>l>>r,v[l].pb(r),v[r].pb(l);
    dfs(1,0);
    for(int i=1; i<17; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=1; i<=m; i++)
        cin>>b[i];
    for(int i=1; i<=k; i++)
        cin>>a[i].a>>a[i].b,a[i].c=i;
    sort(a+1,a+1+k,cmp);
    l=1;
    r=0;
    build(1,1,n);
    build2(1,1,m);
    for(int i=1; i<=k; i++)
    {
        // cout<<a[i].c<<" cucu"<<" "<<l<<" "<<r,down
        go(a[i].a,a[i].b);
        s3=get_lca(1,1,m,a[i].a,a[i].b);
        ans[a[i].c]=s4+depth[1]-depth[s3];
    }
    for(int i=1; i<=k; i++)
        cout<<ans[i],down
    }
/*
8 8 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
2 8
*/

Compilation message

tourism.cpp:17:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const int inf=1e18;
      |               ^~~~
tourism.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main()
      | ^~~~
tourism.cpp: In function 'void build(int, int, int)':
tourism.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int mid=l+r>>1;
      |             ~^~
tourism.cpp: In function 'void upd(int, int, int, int, int, int)':
tourism.cpp:92:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid=l+r>>1;
      |             ~^~
tourism.cpp: In function 'int get1(int, int, int, int, int)':
tourism.cpp:103:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |     int mid=l+r>>1;
      |             ~^~
tourism.cpp: In function 'int get2(int, int, int, int, int)':
tourism.cpp:110:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |     int mid=l+r>>1;
      |             ~^~
tourism.cpp: In function 'void build2(int, int, int)':
tourism.cpp:164:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |     int mid=l+r>>1;
      |             ~^~
tourism.cpp: In function 'int get_lca(int, int, int, int, int)':
tourism.cpp:173:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  173 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Incorrect 4 ms 14684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Incorrect 4 ms 14684 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Execution timed out 5091 ms 23532 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Incorrect 103 ms 19356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 14848 KB Output is correct
3 Correct 6 ms 14684 KB Output is correct
4 Execution timed out 5096 ms 20388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 1 ms 14684 KB Output is correct
3 Correct 1 ms 14684 KB Output is correct
4 Incorrect 4 ms 14684 KB Output isn't correct
5 Halted 0 ms 0 KB -