Submission #1076591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076591		anango	Beech Tree (IOI23_beechtree)	C++17	51 / 100	1804 ms	2097152 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rng;


void prmap(map<int,int> mp) {
    for (auto i:mp) {
        cout << i.first <<":"<<i.second<<", ";
    }
    cout << endl;
}

std::vector<signed> beechtree(signed N, signed M, std::vector<signed> P, std::vector<signed> C) {
    int n=N; int m=M;
    //if any vertex has 2 children with same color then it jambloats
    //also any vertex must be before its child in ordering since if ind[parent]>ind[child] then there are
    //ind[parent]-1 edges considered for child contradiction hyperbloat
    //also consider in the order of a permutation, for each color, it starts being on and turns off at some point
    //in the edges leading from a node to its children
    //thus consider the vertices which have each color in children, and make an ordering
    //if the ordering is consistent, hope it works
    //insufficient
    //increasing order of subtree size?
    //add condition that if color of par[x]->x and color of par[y]->y are the same, put from the par with larger subtree into par with smaller subtree
    //this also deals with the 2 children same color thing
    
    vector<int> subsize(n,1);
    vector<vector<int>> subtree(n);
    vector<vector<int>> sons(n);
    for (int i=0; i<n; i++) subtree[i] = {i};
    int subtask2 = 1;
    int subtask4 = 0;
    map<int,int> freq;
    for (int i=0; i<n; i++) {
        freq[C[i]]++;
    }
    int ma = -1;
    for (auto i:freq) ma=max(ma,i.second);
    if (ma<=2) {
        subtask4=1;
    }
    for (int i=1; i<n; i++) {
        if (P[i]!=i-1) subtask2=0;
    }
    
    if (subtask2) {
        vector<int> ans(n,0);
        ans[n-1] = 1;
        for (int i=n-2; i>=0; i--) {
            ans[i] = ans[i+1] & ((i==n-2 || C[i+1]==C[i+2]));
        }
        vector<signed> ans2(ans.begin(), ans.end());
        return ans2;
    }

    for (int i=n-1; i>=1; i--) {
        subsize[P[i]]+=subsize[i];
        for (int j:subtree[i]) {
            subtree[P[i]].push_back(j);
            if (subtask4 && subtree[P[i]].size()>1600) {
                break;
            }
        }
        sons[P[i]].push_back(i);
    }
    vector<int> ans(n,1);
    for (int root=0; root<n; root++) {
        if (subtask4 && subsize[root]>=1600) {
            ans[root] = rng();
            continue;
        }
        vector<int> relevant=subtree[root];
        map<int,int> revcoords;
        for (int j=0; j<relevant.size(); j++) {
            revcoords[relevant[j]] = j;
        }
        /*vector<vector<int>> adjlist(relevant.size());
        vector<vector<int>> sonsv2(relevant.size());
        for (int i:relevant) {
            for (int j:sons[i]) {
                adjlist[revcoords[i]].push_back(revcoords[j]);
                sonsv2[revcoords[i]].push_back(revcoords[j]);
            }
        }
        for (int j=1; j<dep1.size(); j++) {
            if (subsize[relevant[dep1[j-1]]]<subsize[relevant[dep1[j]]]) {
                adjlist[dep1[j]].push_back(dep1[j-1]);
            }
        }
        map<int,vector<int>> revcols;
        for (int i:relevant) {
            if (i!=root) {
                revcols[C[i]].push_back(revcoords[i]);
            }
        }
        for (auto i:revcols) {
            vector<int> dep1 = i.second;
            sort(dep1.begin(), dep1.end(), [&](const int i1, const int i2) {
                return subsize[relevant[i1]]<subsize[relevant[i2]]
            });
            for (int j=1; j<dep1.size(); j++) {
                if (subsize[relevant[dep1[j-1]]]<subsize[relevant[dep1[j]]]) {
                    adjlist[dep1[j]].push_back(dep1[j-1]);
                }
            }
        }*/
       
        vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
        sort(dep1.begin(), dep1.end(), [&](const int i1, const int i2) {
            return subsize[relevant[i1]]<subsize[relevant[i2]];
        });
        reverse(dep1.begin(), dep1.end());
        map<int,int> colors;
        int fail = 0;
        for (int i=0; i<dep1.size(); i++) {
            int node = dep1[i];
            set<int> subbers;
            map<int,int> colors2;
            for (int j:sons[relevant[node]]) {
                subbers.insert(C[j]);
                if (i>0 && colors[C[j]]<subsize[j]) {
                    fail=1;
                }
                colors2[C[j]] = subsize[j];
            }
            colors=colors2;
            if (subbers.size()<sons[relevant[node]].size()) {
                fail=1;
            }
            //cout << "DOING " << root <<" " << i << " " << node << endl;
            //prmap(colors);
        }
        ans[root] = 1-fail;
        
    }
    vector<signed> ans2(ans.begin(), ans.end());
    return ans2;
}

Compilation message (stderr)

beechtree.cpp: In function 'std::vector<int> beechtree(int, int, std::vector<int>, std::vector<int>)':
beechtree.cpp:76:24: 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]
   76 |         for (int j=0; j<relevant.size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~
beechtree.cpp:110:42: 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 |         vector<int> dep1; for (int i=0; i<relevant.size(); i++) dep1.push_back(i);
      |                                         ~^~~~~~~~~~~~~~~~
beechtree.cpp:117:24: 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]
  117 |         for (int i=0; i<dep1.size(); i++) {
      |                       ~^~~~~~~~~~~~
beechtree.cpp:16:18: warning: unused variable 'm' [-Wunused-variable]
   16 |     int n=N; int m=M;
      |                  ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 0 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12