oj.uz

답안 #364247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364247 2021-02-08T15:07:43 Z inwbear 수도 (JOI20_capital_city) C++14
30 / 100
 1054 ms 34796 KB 
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define L (idx*2)
#define R (idx*2)+1
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,a,b,k,t[200005],ss,arr[200005],ans,l[200005],r[200005],nn[200005],lz[800005],seq[800005],seq1[800005],lz1[800005],c,kk;
vector<int>v[200005];
void gen(int N,int pr,int cc)
{
    arr[cc]=t[N];
    for(int i=0;i<v[N].size();i++)
    {
        if(v[N][i]!=pr)
        {
            gen(v[N][i],N,cc+1);
        }
    }
    return;
}
void up_seq(int st,int ed,int idx,int ll,int rr,int val)
{
    int mid=(st+ed)/2;
    if(lz[idx]!=0)
    {
        seq[idx]+=lz[idx];
        if(st!=ed)
        {
            lz[L]+=lz[idx];
            lz[R]+=lz[idx];
        }
        lz[idx]=0;
    }
    if(st>rr||ed<ll)return;
    if(ll<=st&&rr>=ed)
    {
        seq[idx]+=val;
        if(st!=ed)
        {
            lz[L]+=val;
            lz[R]+=val;
        }
        return;
    }
    up_seq(st,mid,L,ll,rr,val);
    up_seq(mid+1,ed,R,ll,rr,val);
    seq[idx]=max(seq[L],seq[R]);
}
int mx_seq(int st,int ed,int idx,int ll,int rr)
{
    int mid=(st+ed)/2;
    if(lz[idx]!=0)
    {
        seq[idx]+=lz[idx];
        if(st!=ed)
        {
            lz[L]+=lz[idx];
            lz[R]+=lz[idx];
        }
        lz[idx]=0;
    }
    if(st>rr||ed<ll)return -1;
    if(ll<=st&&rr>=ed)return seq[idx];
    return max(mx_seq(st,mid,L,ll,rr),mx_seq(mid+1,ed,R,ll,rr));
}
void up_seq1(int st,int ed,int idx,int ll,int rr,int val)
{
    int mid=(st+ed)/2;
    if(lz1[idx]!=0)
    {
        seq1[idx]+=lz1[idx];
        if(st!=ed)
        {
            lz1[L]+=lz1[idx];
            lz1[R]+=lz1[idx];
        }
        lz1[idx]=0;
    }
    if(st>rr||ed<ll)return;
    if(ll<=st&&rr>=ed)
    {
        seq1[idx]+=val;
        if(st!=ed)
        {
            lz1[L]+=val;
            lz1[R]+=val;
        }
        return;
    }
    up_seq1(st,mid,L,ll,rr,val);
    up_seq1(mid+1,ed,R,ll,rr,val);
    seq[idx]=max(seq[L],seq[R]);
}
int mx_seq1(int st,int ed,int idx,int ll,int rr)
{
    int mid=(st+ed)/2;
    if(lz1[idx]!=0)
    {
        seq1[idx]+=lz1[idx];
        if(st!=ed)
        {
            lz1[L]+=lz1[idx];
            lz1[R]+=lz1[idx];
        }
        lz1[idx]=0;
    }
    if(st>rr||ed<ll)return -1;
    if(ll<=st&&rr>=ed)return seq1[idx];
    return max(mx_seq1(st,mid,L,ll,rr),mx_seq1(mid+1,ed,R,ll,rr));
}
int main()
{
    scanf("%d %d",&n,&k);
    ans=k-1;
    for(int i=1;i<n;i++)
    {
        scanf("%d %d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t[i]);
        if(v[i].size()==1)ss=i;
    }
    gen(ss,0,1);
    for(int i=1;i<=n;i++)
    {
        nn[arr[i]]++;
        if(nn[arr[i]]==1)
        {
            l[arr[i]]=i;
        }
        r[arr[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        up_seq(1,n,1,i,i,i-1);
    }
    for(int i=1;i<=n;i++)
    {
        if(r[arr[i]]==i)
        {
            //printf("==%d %d\n",l[arr[i]],nn[arr[i]]);
            up_seq(1,n,1,1,l[arr[i]],nn[arr[i]]);
            up_seq1(1,n,1,1,l[arr[i]],1);
        }
        else continue;
        a=1,b=i,kk=0;
        //printf("%d\n",mx_seq(1,n,1,1,i));
        if(mx_seq(1,n,1,1,i)!=i)continue;
        while(a<=b)
        {
            c=(a+b)/2;
            if(mx_seq(1,n,1,c,i)==i)
            {
                kk=max(kk,c);
                a=c+1;
            }
            else
            {
                b=c-1;
            }
        }
        ans=min(ans,mx_seq1(1,n,1,kk,kk)-1);
    }
    printf("%d",ans);
}

Compilation message

capital_city.cpp: In function 'void gen(int, int, int)':
capital_city.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[N].size();i++)
      |                 ~^~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |         scanf("%d",&t[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1018 ms 32448 KB Output is correct
2 Correct 966 ms 32384 KB Output is correct
3 Correct 1054 ms 32304 KB Output is correct
4 Correct 1012 ms 32336 KB Output is correct
5 Correct 991 ms 32252 KB Output is correct
6 Correct 966 ms 32296 KB Output is correct
7 Correct 935 ms 31948 KB Output is correct
8 Correct 820 ms 31560 KB Output is correct
9 Correct 272 ms 34796 KB Output is correct
10 Correct 258 ms 34732 KB Output is correct
11 Correct 268 ms 34796 KB Output is correct
12 Correct 276 ms 34796 KB Output is correct
13 Correct 250 ms 34796 KB Output is correct
14 Correct 252 ms 34668 KB Output is correct
15 Correct 277 ms 34720 KB Output is correct
16 Correct 255 ms 34788 KB Output is correct
17 Correct 278 ms 34792 KB Output is correct
18 Correct 267 ms 34668 KB Output is correct
19 Correct 252 ms 34796 KB Output is correct
20 Correct 259 ms 34668 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct

Subtask #4
0 / 59.0

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