Submission #800382

#	Time	Username	Problem	Language	Result	Execution time	Memory
800382		1075508020060209tc	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	557 ms	40404 KiB

joi2019_ho_t5

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
//#define int long long

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

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 ar[200005];
int buc[200005];
int bcnt;
void add(int v){
    buc[v]++;
    if(buc[v]==1){bcnt++;}
    //cout<<v<<" "<<bcnt<<endl;
}
void del(int v){
    buc[v]--;
    if(buc[v]==0){bcnt--;}
   // cout<<v<<" "<<bcnt<<endl;
}
stack<int>stk;


int ans[200005];
void dfs(int nw,int pa){
if(e[nw].size()==1&&pa){
    ans[nw]=max(ans[nw],bcnt);
    return;
}
int d=0;
if(e[nw].size()>=2&&e[nw][1]!=pa){
    d=dph[dp[e[nw][1]]]-dph[nw];
}
while(stk.size()&&dph[stk.top()]>=dph[nw]-d){del(ar[stk.top()]);stk.pop();}
add(ar[nw]);
stk.push(nw);
dfs(e[nw][0],nw);
if(stk.size()&&stk.top()==nw){stk.pop();del(ar[nw]);}
d=dph[dp[e[nw][0]]]-dph[nw];
while(stk.size()&&dph[stk.top()]>=dph[nw]-d){del(ar[stk.top()]);stk.pop();}
ans[nw]=max(ans[nw],bcnt);
for(int i=1;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    add(ar[nw]);
    stk.push(nw);
    dfs(e[nw][i],nw);
    if(stk.size()&&stk.top()==nw){stk.pop();del(ar[nw]);}
}
}

void solve(int rt){
bcnt=0;
while(stk.size()){stk.pop();}
for(int i=1;i<=n;i++){
    buc[i]=0;
}
dpdfs(rt,0);
srtlng(rt);
dfs(rt,0);
}


signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
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>>ar[i];}
finrt();
//cout<<rt1<<endl;
solve(rt1);
//cout<<endl;

//cout<<rt2<<endl;
solve(rt2);
//cout<<rt1<<" "<<rt2<<endl;
for(int i=1;i<=n;i++){
    cout<<ans[i]<<endl;
}
}

Compilation message (stderr)

joi2019_ho_t5.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
joi2019_ho_t5.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
joi2019_ho_t5.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
joi2019_ho_t5.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
joi2019_ho_t5.cpp:60:25: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   60 | void dpdfs(int nw,int pa){
      |                         ^
joi2019_ho_t5.cpp:60:25: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:60:25: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:60:25: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp: In function 'void dpdfs(int, int)':
joi2019_ho_t5.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: At global scope:
joi2019_ho_t5.cpp:74:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   74 | void finrt(){
      |            ^
joi2019_ho_t5.cpp:74:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:74:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:74:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:84:19: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   84 | void srtlng(int rt){
      |                   ^
joi2019_ho_t5.cpp:84:19: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:84:19: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:84:19: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp: In function 'void srtlng(int)':
joi2019_ho_t5.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i=1;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: At global scope:
joi2019_ho_t5.cpp:106:15: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  106 | void add(int v){
      |               ^
joi2019_ho_t5.cpp:106:15: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:106:15: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:106:15: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:111:15: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  111 | void del(int v){
      |               ^
joi2019_ho_t5.cpp:111:15: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:111:15: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:111:15: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:120:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  120 | void dfs(int nw,int pa){
      |                       ^
joi2019_ho_t5.cpp:120:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:120:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:120:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:137:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 | for(int i=1;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t5.cpp: At global scope:
joi2019_ho_t5.cpp:147:18: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  147 | void solve(int rt){
      |                  ^
joi2019_ho_t5.cpp:147:18: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:147:18: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:147:18: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:159:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  159 | signed main(){
      |             ^
joi2019_ho_t5.cpp:159:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:159:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
joi2019_ho_t5.cpp:159:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32