oj.uz

Submission #800269

# Submission time Handle Problem Language Result Execution time Memory
800269 2023-08-01T12:55:52 Z 1075508020060209tc Unique Cities (JOI19_ho_t5) C++14
64 / 100
 884 ms 68956 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC targent("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SGTR{
int l;int r;
int lz;
int mn;
int f;
}tr[800055];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].f=r-l+1;
tr[nw].lz=0;
tr[nw].mn=0;
if(l==r){return;}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);buildtr(nw*2+1,mi+1,r);
}
void psh(int nw){
int v=tr[nw].lz;
tr[nw].lz=0;
tr[nw*2].lz+=v;tr[nw*2+1].lz+=v;
tr[nw*2].mn+=v;tr[nw*2+1].mn+=v;
}
int qmn(int nw,int l,int r){
if(r<l){return 1e9;}
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mn;
}
if(tr[nw].l>r||tr[nw].r<l){return 1e9;}
psh(nw);
return min(qmn(nw*2,l,r),qmn(nw*2+1,l,r));
}

void upd(int nw,int l,int r,int v){
if(r<l){return;}
if(tr[nw].l>=l&&tr[nw].r<=r){
    tr[nw].mn+=v;tr[nw].lz+=v;
    return;
}
if(tr[nw].l>r||tr[nw].r<l){return;}
psh(nw);
upd(nw*2,l,r,v);upd(nw*2+1,l,r,v);
tr[nw].mn=min(tr[nw*2].mn,tr[nw*2+1].mn);
tr[nw].f=0;
if(tr[nw*2].mn==tr[nw].mn){
    tr[nw].f+=tr[nw*2].f;
}
if(tr[nw*2+1].mn==tr[nw].mn){
    tr[nw].f+=tr[nw*2+1].f;
}
}

int qmnf(int nw,int l,int r){
if(r<l){return 0;}
if(tr[nw].l>=l&&tr[nw].r<=r){
    if(tr[nw].mn==0){
        return tr[nw].f;
    }return 0;
}
if(tr[nw].r<l||tr[nw].l>r){return 0;}
psh(nw);
return qmnf(nw*2,l,r)+qmnf(nw*2+1,l,r);
}

int n;int M;
vector<int>e[500005];
int D;
int rt1;int rt2;
int dph[500005];
int dp[500005];
int fa[500005];

void dpdfs(int nw,int pa){
fa[nw]=pa;
dph[nw]=dph[pa]+1;
dp[nw]=nw;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dpdfs(v,nw);
    if(dph[dp[v]]>dph[dp[nw]]){
        dp[nw]=dp[v];
    }
}
}

void finrt(){
dpdfs(1,0);
rt1=dp[1];
//cout<<rt1<<" ";
dpdfs(rt1,0);
rt2=dp[rt1];
//cout<<rt2<<endl;
D=dph[rt2];
}

void srtlng(int rt){
dpdfs(rt,0);
for(int nw=1;nw<=n;nw++){
    for(int i=0;i<e[nw].size();i++){
        int v=e[nw][i];
        if(v==fa[nw]){continue;}
        if(e[nw][0]==fa[nw]||dph[dp[v]]>dph[dp[e[nw][0]]]){
            swap(e[nw][i],e[nw][0]);
        }
    }
    for(int i=1;i<e[nw].size();i++){
        int v=e[nw][i];
        if(v==fa[nw]){continue;}
        if(e[nw][1]==fa[nw]||dph[dp[v]]>dph[dp[e[nw][1]]]){
            swap(e[nw][i],e[nw][1]);
        }
    }
}
}
int ans[500005];
void dfs(int nw,int pa){
int askr=dph[nw]-1-(dph[dp[nw]]-dph[nw]);
/*
if(qmn(1,1,askr)==0){ans[nw]=1;}
*/
ans[nw]=max(ans[nw],qmnf(1,1,askr));
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    if(i!=0){
        int d=dph[dp[nw]]-dph[nw];
        upd(1,dph[nw]-d,dph[nw]-1,1);
        dfs(v,nw);
        upd(1,dph[nw]-d,dph[nw]-1,-1);
    }else{
        int d=0;
        if(e[nw].size()>=2&&e[nw][1]!=pa){
            d=dph[dp[e[nw][1]]]-dph[nw];
        }
        upd(1,dph[nw]-d,dph[nw]-1,1);
        dfs(v,nw);
        upd(1,dph[nw]-d,dph[nw]-1,-1);
    }
}
}

void solve(int rt){
dpdfs(rt,0);
srtlng(rt);
buildtr(1,1,n);
dfs(rt,0);
}


signed main(){
cin>>n>>M;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b;
    e[a].push_back(b);
    e[b].push_back(a);
}
for(int i=1;i<=n;i++){cin>>M;}
finrt();
solve(rt1);
solve(rt2);
//cout<<rt1<<" "<<rt2<<endl;
for(int i=1;i<=n;i++){
    if(M==1){
        ans[i]=min(ans[i],1ll);
    }
    cout<<ans[i]<<endl;
}
}

Compilation message

joi2019_ho_t5.cpp:2: warning: ignoring '#pragma GCC targent' [-Wunknown-pragmas]
    2 | #pragma GCC targent("avx,popcnt,sse4,abm")
      | 
joi2019_ho_t5.cpp: In function 'void dpdfs(long long int, long long int)':
joi2019_ho_t5.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void srtlng(long long int)':
joi2019_ho_t5.cpp:103:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp:110:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=1;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'void dfs(long long int, long long int)':
joi2019_ho_t5.cpp:126:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 11 ms 12324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 31980 KB Output is correct
2 Correct 340 ms 42036 KB Output is correct
3 Correct 77 ms 18136 KB Output is correct
4 Correct 714 ms 49468 KB Output is correct
5 Correct 749 ms 67120 KB Output is correct
6 Correct 711 ms 58036 KB Output is correct
7 Correct 692 ms 49356 KB Output is correct
8 Correct 717 ms 51316 KB Output is correct
9 Correct 819 ms 50860 KB Output is correct
10 Correct 815 ms 50608 KB Output is correct
11 Correct 603 ms 50024 KB Output is correct
12 Correct 848 ms 61012 KB Output is correct
13 Correct 884 ms 58268 KB Output is correct
14 Correct 831 ms 57488 KB Output is correct
15 Correct 679 ms 49864 KB Output is correct
16 Correct 727 ms 61472 KB Output is correct
17 Correct 722 ms 58128 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 46484 KB Output is correct
2 Correct 699 ms 67268 KB Output is correct
3 Correct 81 ms 18756 KB Output is correct
4 Correct 761 ms 50340 KB Output is correct
5 Correct 750 ms 68956 KB Output is correct
6 Correct 732 ms 59280 KB Output is correct
7 Correct 707 ms 50416 KB Output is correct
8 Correct 793 ms 54560 KB Output is correct
9 Correct 822 ms 53032 KB Output is correct
10 Correct 755 ms 51876 KB Output is correct
11 Correct 660 ms 50444 KB Output is correct
12 Correct 820 ms 65740 KB Output is correct
13 Correct 825 ms 58488 KB Output is correct
14 Correct 789 ms 58308 KB Output is correct
15 Correct 620 ms 50976 KB Output is correct
16 Correct 720 ms 62868 KB Output is correct
17 Correct 714 ms 59292 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Incorrect 11 ms 12324 KB Output isn't correct
3 Halted 0 ms 0 KB -