Submission #1294737


Source Code Expand

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

static class Program
{
    static void Main()
    {
        new Magatro().Solve();
    }
}

class Node
{
    public int Num;//いるかな?
    public List<int> Parent = new List<int>();//Parent[i] 2^i個上
    public int Depth;
}

class Magatro
{
    private int N;
    List<int>[] R;
    Node[] Tree;
    private int Q;

    private void MakeTree()
    {
        Tree = new Node[N];
        for (int i = 0; i < N; i++)
        {
            Tree[i] = new Node();
            Tree[i].Num = i;
        }
        Tree[0].Num = 0;
        Tree[0].Depth = 0;
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);
        while (q.Count > 0)//木
        {
            int d = q.Dequeue();
            foreach (int i in R[d])
            {
                if (Tree[d].Parent.Count > 0 && i == Tree[d].Parent[0])
                {
                    continue;
                }
                Tree[i].Parent.Add(d);
                Tree[i].Depth = Tree[d].Depth + 1;
                q.Enqueue(i);
            }
        }
        for (int i = 1; i < N; i <<= 1)//2^kこ前
        {
            foreach (var n in Tree)
            {
                if (n.Depth >= i * 2)
                {
                    n.Parent.Add(Tree[n.Parent[i / 2]].Parent[i / 2]);
                }
            }
        }
    }

    private int Query(int a, int b)
    {
        int res = 0;

        if (Tree[a].Depth > Tree[b].Depth)
        {
            a ^= b;
            b ^= a;
            a ^= b;
        }

        int sa = Tree[b].Depth - Tree[a].Depth;
        for (int i = 0; sa > 0; sa /= 2, i++)//高さ合わせる
        {
            if (sa % 2 == 1)
            {
                b = Tree[b].Parent[i];
                res += 1 << i;
            }
        }

        if (a == b)
        {
            return res;
        }

        while (true)
        {
            int j = -1;
            for (int i = 0; i < Tree[a].Parent.Count; i++)
            {
                if (Tree[a].Parent[i] == Tree[b].Parent[i])
                {
                    break;
                }
                j = i;
            }
            if(j == -1)
            {
                res += 2;
                break;
            }
            else
            {
                a = Tree[a].Parent[j];
                b = Tree[b].Parent[j];
                res += 1 << (j+1);
            }
        }

        return res;
    }

    public void Solve()
    {
        N = int.Parse(Console.ReadLine());
        R = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            R[i] = new List<int>();
        }
        for (int i = 0; i < N - 1; i++)
        {
            var line = Console.ReadLine().Split(' ');
            int x = int.Parse(line[0]) - 1;
            int y = int.Parse(line[1]) - 1;
            R[x].Add(y);
            R[y].Add(x);
        }
        MakeTree();
        Q = int.Parse(Console.ReadLine());
        for (int i = 0; i < Q; i++)
        {
            var line = Console.ReadLine().Split(' ');
            int a = int.Parse(line[0]) - 1;
            int b = int.Parse(line[1]) - 1;
            Console.WriteLine(Query(a, b) + 1);
        }
    }
}

Submission Info

Submission Time
Task D - 閉路
User mban
Language C# (Mono 4.6.2.0)
Score 0
Code Size 3389 Byte
Status RE
Exec Time 682 ms
Memory 40164 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 2
RE × 10
AC × 7
RE × 20
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
Subtask1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 26 ms 11604 KB
subtask0_sample02.txt AC 24 ms 11348 KB
subtask0_sample03.txt AC 24 ms 11348 KB
subtask1_01.txt RE 175 ms 36972 KB
subtask1_02.txt RE 163 ms 38688 KB
subtask1_03.txt AC 23 ms 11348 KB
subtask1_04.txt AC 23 ms 11348 KB
subtask1_05.txt RE 24 ms 10848 KB
subtask1_06.txt RE 24 ms 8928 KB
subtask1_07.txt RE 231 ms 36068 KB
subtask1_08.txt RE 229 ms 34196 KB
subtask1_09.txt RE 227 ms 37100 KB
subtask1_10.txt RE 221 ms 36972 KB
subtask1_11.txt RE 216 ms 36972 KB
subtask1_12.txt RE 226 ms 34924 KB
subtask2_01.txt RE 162 ms 36640 KB
subtask2_02.txt RE 162 ms 32876 KB
subtask2_03.txt AC 657 ms 15680 KB
subtask2_04.txt AC 682 ms 15804 KB
subtask2_05.txt RE 24 ms 8928 KB
subtask2_06.txt RE 24 ms 10848 KB
subtask2_07.txt RE 229 ms 40164 KB
subtask2_08.txt RE 247 ms 35160 KB
subtask2_09.txt RE 219 ms 39016 KB
subtask2_10.txt RE 221 ms 36776 KB
subtask2_11.txt RE 216 ms 34924 KB
subtask2_12.txt RE 220 ms 36972 KB