제출 #905167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
905167		jay_jayjay	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2047 ms	66992 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
#define all(x) (x).begin(),(x).end()

int main() {
        int n,m;scanf("%d%d",&n,&m);
        
        vector<vector<int>> adj(n);
        for(int i=1;i<n;i++) {
                int u,v;scanf("%d%d",&u,&v);u--;v--;
                adj[u].push_back(v); adj[v].push_back(u);
        }
        
        vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--;
        
        // ;-;
        vector<int> sz(n),dep(n),mxdep(n),val(n);
        auto dfs1 = [&](auto self, int v, int p=-1, int rk=0)  -> void {
                sz[v]=1; dep[v]=rk; mxdep[v]=0;
                for(auto x:adj[v]) if(x!=p)
                        self(self,x,v,rk+1),
                        sz[v]+=sz[x],
                        mxdep[v]=max(mxdep[v],mxdep[x]+1);
        };
        
        vector<int> S(m); int cnt=0;
        auto add = [&](int x, int d) {
                // printf("\t\tadd %d %d\n",x,d);
                cnt-=S[x]>0;
                S[x]+=d;
                cnt+=S[x]>0;
        };
        vector<int> A;
        vector<array<int,2>> B;
        auto dfs2 = [&](auto self, int v, int p=-1) -> void {
                sort(all(adj[v]), [&](int a, int b) { return mxdep[a] > mxdep[b]; });
                assert(p == -1 || adj[v][0] == p);
                if(p==-1) adj[v].insert(adj[v].begin(),-1);
                
                // printf("%d: ", v);
                // for(auto x:A)printf("%d ",x);
                // printf("\n");
                // for(auto x:B)printf("%d|%d ", x[0],x[1]);
                // printf("\n");
                
                vector<array<int,2>> R;
                for(int i=1;i<adj[v].size();i++) {
                        int x = adj[v][i];
                        
                        int d=0;
                        if(i > 1) d=mxdep[adj[v][1]]+1;
                        else if(adj[v].size() > 2) d=mxdep[adj[v][2]]+1;
                        // printf("\t\t\tv=%d x=%d d=%d\n",v,x,d);
                        // printf("\t\t\tcut %d\n", dep[v]-d);
                        
                        while(B.size() && B.back()[0] >= dep[v] - d) {
                                R.push_back(B.back());
                                add(B.back()[1], -1);
                                B.pop_back();
                        }
                        B.push_back({dep[v], c[v]});
                        add(c[v],1);
                        A.push_back(d);
                        
                        self(self, x, v);
                        
                        A.pop_back();
                        B.pop_back();
                        add(c[v],-1);
                }
                if(adj[v].size()>1) {
                        int d=mxdep[adj[v][1]]+1;
                        // printf("\t\t\texit d=%d\n", adj[v][1]);
                        while(B.size() && B.back()[0] >= dep[v] - d) {
                                R.push_back(B.back());
                                add(B.back()[1], -1);
                                B.pop_back();
                        }
                }
                // printf("%d exit: ", v);
                // for(auto x:A)printf("%d ",x);
                // printf("(%d)\n", adj[v].size()>1?adj[v][1]:0);
                // for(auto x:B)printf("%d|%d ", x[0],x[1]);
                // printf("\n");
                // for(int i=0;i<m;i++)printf("%d ",S[i]);
                // printf("\n");
                val[v] = max(val[v],cnt);
                while(R.size()) {
                        B.push_back(R.back());
                        add(B.back()[1], 1);
                        R.pop_back();
                }
                if(p==-1)adj[v].erase(adj[v].begin());
        };
        
        // find dia
        dfs1(dfs1, 0);
        int v1 = max_element(all(dep)) - dep.begin();
        dfs1(dfs1, v1);
        int v2 = max_element(all(dep)) - dep.begin();
        
        // printf("dia is %d, %d\n", v1, v2);
        
        dfs2(dfs2,v1);
        dfs1(dfs1,v2);
        dfs2(dfs2,v2);
        for(int i=0;i<n;i++)printf("%d ",val[i]);
        printf("\n");
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t5.cpp: In instantiation of 'main()::<lambda(auto:24, int, int)> [with auto:24 = main()::<lambda(auto:24, int, int)>]':
joi2019_ho_t5.cpp:108:21:   required from here
joi2019_ho_t5.cpp:51:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int i=1;i<adj[v].size();i++) {
      |                             ~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:10:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         int n,m;scanf("%d%d",&n,&m);
      |                 ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:14:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 int u,v;scanf("%d%d",&u,&v);u--;v--;
      |                         ~~~~~^~~~~~~~~~~~~~
joi2019_ho_t5.cpp:18:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         vector<int> c(n);for(auto&x:c)scanf("%d",&x),x--;
      |                                       ~~~~~^~~~~~~~~

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