oj.uz

Submission #905167

# Submission time Handle Problem Language Result Execution time Memory
905167 2024-01-12T16:59:09 Z jay_jayjay Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 66992 KB 
#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");
}

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 6 ms 696 KB Output is correct
4 Correct 6 ms 820 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 18 ms 1112 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 16 ms 1088 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 1 ms 564 KB Output is correct
17 Correct 9 ms 860 KB Output is correct
18 Correct 6 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 18 ms 1116 KB Output is correct
21 Correct 7 ms 860 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 448 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 392 KB Output is correct
27 Correct 10 ms 1212 KB Output is correct
28 Correct 8 ms 860 KB Output is correct
29 Correct 4 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 10 ms 860 KB Output is correct
32 Correct 6 ms 860 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10868 KB Output is correct
2 Execution timed out 2019 ms 39388 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 16212 KB Output is correct
2 Execution timed out 2047 ms 66992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 6 ms 696 KB Output is correct
4 Correct 6 ms 820 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 18 ms 1112 KB Output is correct
7 Correct 7 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 16 ms 1088 KB Output is correct
14 Correct 4 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 1 ms 564 KB Output is correct
17 Correct 9 ms 860 KB Output is correct
18 Correct 6 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 18 ms 1116 KB Output is correct
21 Correct 7 ms 860 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 2 ms 448 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 392 KB Output is correct
27 Correct 10 ms 1212 KB Output is correct
28 Correct 8 ms 860 KB Output is correct
29 Correct 4 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 10 ms 860 KB Output is correct
32 Correct 6 ms 860 KB Output is correct
33 Correct 83 ms 10868 KB Output is correct
34 Execution timed out 2019 ms 39388 KB Time limit exceeded
35 Halted 0 ms 0 KB -