oj.uz

Submission #1043200

# Submission time Handle Problem Language Result Execution time Memory
1043200 2024-08-04T04:49:18 Z model_code Team Coding (EGOI24_teamcoding) C++17
62 / 100
 4000 ms 204076 KB 
#include<bits/stdc++.h>

using namespace std;
typedef vector<int> vi;


void dfs(int v, int p,vector<vi>& adj, vi& level,vi& order){
  if(v!= 0)
  	level[v]=level[p]+1;
  for(int w:adj[v]){
    dfs(w,v,adj,level,order);
  }
  order.push_back(v);
}
void col_tree(int v, int p, vector<vi>& adj, vi& col, vector<vi>& col_adj, vi& cur_p,vector<queue<int>>& col_root) {
	if(cur_p[col[v]] == -1) {
		col_root[col[v]].push(v);
	} else {
		col_adj[cur_p[col[v]]].push_back(v);
	}
	int old = cur_p[col[v]];
	cur_p[col[v]] = v;
	for(int w:adj[v]){
		if(w==p) continue;
		col_tree(w,v,adj,col,col_adj,cur_p,col_root);
	}
	cur_p[col[v]] = old;

}



signed main(){
	cin.tie(0)-> sync_with_stdio(false);
	int n,k;
	cin >> n >> k;

	vi col(n);
	vector<vi> col_v(k);
	for(int i=0;i<n;++i){
		cin >> col[i];
		col_v[col[i]].push_back(i);
	}
	
        vector<vi> adj(n);
	for(int i=0;i<n-1;++i){
		int u,v;
		u = i+1;
		cin >> v;
		adj[v].push_back(u);
	}
        vi order;
	vi v_level(n,0);
        dfs(0,-1,adj,v_level,order);        


	vector<vi> col_adj(n);
	vector<queue<int>> col_root(k);
	vi col_p(k,-1);

	col_tree(0,-1,adj,col,col_adj, col_p, col_root);
	cerr << "coltree solved" <<'\n';


	vector<unordered_map<int,int>> col_count(k);
	for(int i=0;i<n;++i){
		auto  search = col_count[col[i]].find(v_level[i]);
		if(search == col_count[col[i]].end()) col_count[col[i]][v_level[i]]=1;
		else search->second++;
	}

	int val = 0;
	int swaps = 0;
	
	cerr << " starting" << '\n';
        vector<deque<int>>  counts(n);        
        for(int v: order){
            //cout << "vertex " << v << '\n';
            for(int w:adj[v]){
	       	if(counts[w].size() > counts[v].size()) swap(counts[w],counts[v]);
		for(int i=0;i<counts[w].size();++i){
			counts[v][i]+=counts[w][i];
		}
	    }
	    counts[v].push_front(1);
        
            //if v is not color root, skip it
            if(v != col_root[col[v]].front()) continue;
            //cout << v << '\n';
            col_root[col[v]].pop();
        
            
            
            int v_val = 0;
            int v_swaps = 0;
            vi col_lev(n,0);
            vi vis(n,0);
            queue<int> q;
            q.push(v);

            while(!q.empty()){
                    int u = q.front();
                    q.pop();
                    if(v_level[u]<v_level[v]){
                            //cerr << u << ' ' << v_level[u] << '\n';
                            assert(false);
                    }
                    col_lev[v_level[u]]++;
                    for(int w:col_adj[u]) q.push(w);
            }

            for(int u : col_v[col[v]]){
                    //cout << "clv" << u << '\n';
                    int d = v_level[u];
                    if(vis[d]) continue;
                    vis[d]=1;
                    if(d<v_level[v] || d > v_level[v]+counts[v].size()-1) continue;
                    //cout << "root " << v << " level " << d << " col count " << col_count[col[v]][d]<< " level count " << counts[v][d-v_level[v]]<<'\n';
                    int d_val= min(counts[v][d-v_level[v]],col_count[col[v]][d]);
                    v_val += d_val;
                    v_swaps += d_val-col_lev[d];
            }
            if(v_val>val){
                    val=v_val;
                    swaps=v_swaps;
            }
            if(val==v_val)
                    swaps = min(v_swaps,swaps);


    }
            
        

    cout << val << ' ' << swaps<<'\n';

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i=0;i<counts[w].size();++i){
      |               ~^~~~~~~~~~~~~~~~~
Main.cpp:117:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                     if(d<v_level[v] || d > v_level[v]+counts[v].size()-1) continue;
      |                                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 827 ms 144140 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 2140 KB Output is correct
12 Correct 75 ms 96060 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 3 ms 3928 KB Output is correct
15 Correct 1037 ms 177244 KB Output is correct
16 Correct 1 ms 344 KB Output is correct

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2140 KB Output is correct
5 Correct 58 ms 95924 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 2392 KB Output is correct
8 Execution timed out 4075 ms 103724 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 859 ms 144620 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct
11 Correct 1024 ms 177348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 452 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 3 ms 3436 KB Output is correct
16 Correct 3 ms 2652 KB Output is correct
17 Correct 3 ms 4188 KB Output is correct
18 Correct 1712 ms 170892 KB Output is correct
19 Correct 1454 ms 141844 KB Output is correct
20 Correct 1339 ms 103648 KB Output is correct
21 Correct 1462 ms 127280 KB Output is correct
22 Correct 1608 ms 204076 KB Output is correct
23 Correct 1281 ms 132524 KB Output is correct
24 Correct 1594 ms 113400 KB Output is correct
25 Correct 4 ms 2652 KB Output is correct
26 Correct 5 ms 3420 KB Output is correct
27 Correct 5 ms 3672 KB Output is correct
28 Correct 3 ms 4188 KB Output is correct
29 Correct 39 ms 18860 KB Output is correct
30 Correct 1391 ms 151716 KB Output is correct
31 Correct 1388 ms 174836 KB Output is correct
32 Correct 2080 ms 172348 KB Output is correct
33 Correct 1577 ms 182820 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 2136 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 3 ms 3928 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 4 ms 2392 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 5 ms 2652 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 3436 KB Output is correct
24 Correct 4 ms 2652 KB Output is correct
25 Correct 5 ms 4188 KB Output is correct
26 Correct 3 ms 2652 KB Output is correct
27 Correct 3 ms 3412 KB Output is correct
28 Correct 4 ms 3708 KB Output is correct
29 Correct 4 ms 4056 KB Output is correct
30 Correct 7 ms 4188 KB Output is correct
31 Correct 4 ms 2140 KB Output is correct
32 Correct 3 ms 2560 KB Output is correct
33 Correct 2 ms 2652 KB Output is correct
34 Correct 3 ms 3676 KB Output is correct
35 Correct 3 ms 4440 KB Output is correct
36 Correct 3 ms 2652 KB Output is correct
37 Correct 3 ms 3672 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 352 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 352 KB Output is correct

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 827 ms 144140 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 2140 KB Output is correct
12 Correct 75 ms 96060 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 3 ms 3928 KB Output is correct
15 Correct 1037 ms 177244 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 2140 KB Output is correct
21 Correct 58 ms 95924 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 3 ms 2392 KB Output is correct
24 Execution timed out 4075 ms 103724 KB Time limit exceeded
25 Halted 0 ms 0 KB -