Submission #61869594

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Solution
{
    public const int TIME_LIMIT = 1900;
    public static int H;
    public static void Main()
    {
        int[] inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        int n = inputs[0];
        int m = inputs[1];
        H = inputs[2];
        Stopwatch sw = Stopwatch.StartNew();
        List<Node> nodes = Console.ReadLine().Split(' ').Select(int.Parse).Select(b => new Node(b)).ToList();
        for (int i = 0; i < n; i++) nodes[i].ID = i;
        for (int i = 0; i < m; i++)
        {
            inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int a = inputs[0];
            int b = inputs[1];
            nodes[a].Neighbors.Add(nodes[b]);
            nodes[b].Neighbors.Add(nodes[a]);
        }
        for (int i = 0; i < n; i++)
        {
            inputs = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            nodes[i].X = inputs[0];
            nodes[i].Y = inputs[1];
        }

        int score = 0;
        int[] solution = null;
        int runs = 0;
        List<TreeSave> treeSaves = new();
        while (sw.ElapsedMilliseconds < TIME_LIMIT / 2)
        {
            List<Node> used = CreateTree(nodes.ToList());
            treeSaves.Add(new TreeSave(used));
            foreach (Node u in used) u.Revert();
        }
        treeSaves = treeSaves.OrderByDescending(t => t.Average).ToList(); // TODO take 1 for each node at least
        List<TreeSave> allSaves = treeSaves;
        treeSaves = new();
        int[] nodeCovered = new int[n];
        foreach (TreeSave save in allSaves)
        {
            int min = int.MaxValue;
            foreach (int id in save.IDs) min = Math.Min(min, nodeCovered[id]);
            if (min < 5)
            {
                treeSaves.Add(save);
                foreach (int id in save.IDs) nodeCovered[id]++;
            }
        }
        while (sw.ElapsedMilliseconds < TIME_LIMIT)
        {
            runs++;
            long[] mask = new long[1000 / 64 + 1];
            int savesUsed = 0;
            foreach (TreeSave save in treeSaves)
            {
                if (random.Next(5) != 0) continue;
                if (!save.AllowMask(mask)) continue;
                save.AddMask(mask);
                savesUsed++;
                for (int i = 0; i < save.IDs.Length; i++)
                {
                    nodes[save.IDs[i]].Used = true;
                    nodes[save.IDs[i]].Parent = save.Parents[i];
                    nodes[save.IDs[i]].Depth = save.Depths[i];
                }
            }
            List<Node> unused = nodes.Where(n => !n.Used).ToList();
            while (unused.Count > 0)
            {
                CreateHighScoringTree(unused);
                unused = unused.Where(n => !n.Used).ToList();
            }
            int currentScore = 1 + nodes.Sum(n => n.Score());
            Console.Error.WriteLine(currentScore + " " + savesUsed);
            if (currentScore > score)
            {
                score = currentScore;
                solution = nodes.Select(n => n.Parent?.ID ?? -1).ToArray();
            }
            foreach (Node node in nodes) node.Revert();
        }
        Console.Error.WriteLine("score: " + score + "   runs: " + runs);
        Console.WriteLine(string.Join(" ", solution));
    }

    private static void CreateHighScoringTree(List<Node> unused)
    {
        double score = 0;
        List<Node> bestTree = null;
        for (int i = 0; i < 50; i++)
        {
            List<Node> tree = CreateTree(unused);
            double tmpScore = tree.Average(t => t.Score());
            if (tmpScore > score)
            {
                bestTree = tree;
                score = tmpScore;
                foreach (Node node in tree) node.Save();
            }
            foreach (Node node in tree) node.Revert();
        }
        foreach (Node node in bestTree) node.Restore();
    }

    private static Random random = new Random(0);
    private static List<Node> CreateTree(List<Node> unused)
    {
        Node root = unused[random.Next(unused.Count)];
        root.Used = true;
        List<Node> tree = new() { root };
        ExpandTree(root, root, tree);

        List<Node> canShift = tree.Where(n => n.Parent?.Parent != null && n.Neighbors.Contains(n.Parent.Parent)).OrderByDescending(n => n.Depth).ThenBy(n => n.Beauty).ToList();
        foreach (Node s in canShift)
        {
            if (!s.Neighbors.Any(n => !n.Used)) continue;
            s.Depth--;
            s.Parent = s.Parent.Parent;
            ExpandTree(root, s, tree);
        }
        return tree;
    }

    private static void ExpandTree(Node root, Node source, List<Node> tree)
    {
        PriorityQueue<(Node from, Node to), double> queue = new();
        foreach (Node next in source.Neighbors)
        {
            if (next.Used) continue;
            queue.Enqueue((source, next), (next.Beauty + random.Next(10)) / Math.Pow(source.Depth + 2.0, 1.5));
        }
        while (queue.Count > 0)
        {
            var (from, to) = queue.Dequeue();
            if (to.Used) continue;
            to.Parent = from;
            to.Root = root;
            to.Used = true;
            to.Depth = from.Depth + 1;
            tree.Add(to);
            if (to.Depth < H)
            {
                foreach (Node next in to.Neighbors)
                {
                    if (next.Used) continue;
                    queue.Enqueue((to, next), (next.Beauty + random.Next(10)) / Math.Pow(to.Depth + 2.0, 1.5));
                }
            }
        }
    }
}

public class Node
{
    public int ID;
    public int X, Y;
    public int Beauty;
    public List<Node> Neighbors = new();
    public Node Parent;
    public Node Root;
    public bool Used;
    public int Depth;
    public Node(int beauty)
    {
        this.Beauty = beauty;
    }

    public void Revert()
    {
        Parent = null;
        Root = null;
        Used = false;
        Depth = 0;
    }

    private Node parentSave;
    private Node rootSave;
    private int depthSave;
    public void Save()
    {
        parentSave = Parent;
        rootSave = Root;
        depthSave = Depth;
    }

    public void Restore()
    {
        Parent = parentSave;
        Root = rootSave;
        Depth = depthSave;
        Used = true;
    }

    public int Score() => Beauty * (Depth + 1);
    public double Dist(Node n) => Math.Sqrt((X - n.X) * (X - n.X) + (Y - n.Y) * (Y - n.Y));
}

public class TreeSave
{
    public int[] IDs;
    public Node[] Parents;
    public int[] Depths;
    public long[] BitMask = new long[1000 / 64 + 1];
    public double Average;
    public TreeSave(List<Node> used)
    {
        Average = used.Average(n => n.Score());
        IDs = used.Select(n => n.ID).ToArray();
        Parents = used.Select(n => n.Parent).ToArray();
        Depths = used.Select(n => n.Depth).ToArray();
        foreach (int id in IDs) BitMask[id / 64] |= 1L << (id % 64);
    }

    public bool AllowMask(long[] mask)
    {
        for (int i = 0; i < mask.Length; i++)
        {
            if ((mask[i] & this.BitMask[i]) != 0) return false;
        }
        return true;
    }

    public void AddMask(long[] mask)
    {
        for (int i = 0; i < mask.Length; i++) mask[i] |= this.BitMask[i];
    }
}

Submission Info

Judge Result