AtCoder Beginner Contest 354 E

https://atcoder.jp/contests/abc354/tasks/abc354_e

特に工夫もせずにグラフを作ります。それで十分間に合いました。

// Remove Pairs
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

struct Graph {
    g: Vec<usize>
}

impl Graph {
    fn len(&self) -> usize {
        self.g.len()
    }
    
    fn edges(&self) -> Vec<Edge> {
        let mut edges: Vec<Edge> = vec![];
        for u in 0..self.len() {
            if self.g[u] == 0 {
                continue
            }
            for v in u+1..self.len() {
                if ((self.g[u] >> v) & 1) != 0 {
                    edges.push((u, v))
                }
            }
        }
        edges
    }
    
    fn is_isolated(&self) -> bool {
        self.g.iter().all(|&s| s == 0)
    }
    
    fn remove_node(&mut self, v: Node) -> usize {
        let s = self.g[v];
        for i in 0..self.len() {
            if ((s >> i) & 1) == 1 {
                self.g[i] -= 1 << v;
            }
        }
        self.g[v] = 0;
        s
    }
    
    fn resume(&mut self, v: Node, s: usize) {
        for i in 0..self.len() {
            if ((s >> i) & 1) == 1 {
                self.g[i] |= 1 << v
            }
        }
        self.g[v] = s
    }
}


//////////////////// process ////////////////////

type Card = (i32, i32);

fn read_card() -> Card {
    let v = read_vec();
    let (A, B) = (v[0], v[1]);
    (A, B)
}

fn read_input() -> Vec<Card> {
    let N = read();
    let cards: Vec<Card> = (0..N).map(|_| read_card()).collect();
    cards
}

fn add_edges(map: HashMap<i32, usize>, g: &mut Vec<usize>) {
    let N = g.len();
    for (_, s) in map.into_iter() {
        for i in 0..N {
            if ((s >> i) & 1) == 0 {
                continue
            }
            for j in 0..N {
                if i != j && ((s >> j) & 1) == 1 {
                    g[i] |= 1 << j
                }
            }
        }
    }
}

fn make_graph(cards: Vec<Card>) -> Graph {
    let N = cards.len();
    let mut map1: HashMap<i32, usize> = HashMap::new();
    let mut map2: HashMap<i32, usize> = HashMap::new();
    for (i, (A, B)) in cards.into_iter().enumerate() {
        let e1 = map1.entry(A).or_insert(0);
        *e1 |= 1 << i;
        let e2 = map2.entry(B).or_insert(0);
        *e2 |= 1 << i
    }
    let mut g: Vec<usize> = vec![0; N];
    add_edges(map1, &mut g);
    add_edges(map2, &mut g);
    Graph { g }
}

fn wins(s: usize, graph: &mut Graph, memo: &mut HashMap<usize, bool>) -> bool {
    if let Some(b) = memo.get(&s) {
        *b
    }
    else if graph.is_isolated() {
        false
    }
    else {
        for (u, v) in graph.edges().into_iter() {
            let su = graph.remove_node(u);
            let sv = graph.remove_node(v);
            let s1 = s - (1 << u) - (1 << v);
            let b1 = wins(s1, graph, memo);
            graph.resume(v, sv);
            graph.resume(u, su);
            if !b1 {
                memo.insert(s, true);
                return true
            }
        }
        memo.insert(s, false);
        false
    }
}

fn F(cards: Vec<Card>) -> bool {
    let N = cards.len();
    
    let mut graph = make_graph(cards);
    let mut memo: HashMap<usize, bool> = HashMap::new();
    wins((1 << N) - 1, &mut graph, &mut memo)
}

fn main() {
    let cards = read_input();
    println!("{}", (if F(cards) { "Takahashi" } else { "Aoki" }).to_string());
}