結果

問題 No.2301 Namorientation
コンテスト
ユーザー Shirotsume
提出日時 2023-05-09 00:19:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,810 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 701,976 KB
最終ジャッジ日時 2024-11-25 13:34:02
合計ジャッジ時間 69,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 TLE * 15 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, Counter
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353

from collections import deque
class MaxFlow():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []
 
    def add_edge(self, fr, to, cap):
        #assert 0 <= fr < self.n
        #assert 0 <= to < self.n
        #assert 0 <= cap
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
        return m
 
    def get_edge(self, idx):
        #assert 0 <= idx < len(self.pos)
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap = self.graph[to][rev]
        return rev_to, to, cap + rev_cap, rev_cap
 
    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.get_edge(i)
 
    def change_edge(self, idx, new_cap, new_flow):
        #assert 0 <= idx < len(self.pos)
        #assert 0 <= new_flow <= new_cap
        to, rev, cap = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
        self.graph[to][rev][2] = new_flow
 
    def dfs(self, s, v, up):
        if v == s: return up
        res = 0
        lv = self.level[v]
        for i in range(self.iter[v], len(self.graph[v])):
            to, rev, cap = self.graph[v][i]
            if lv <= self.level[to] or self.graph[to][rev][2] == 0: continue
            d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
            if d <= 0: continue
            self.graph[v][i][2] += d
            self.graph[to][rev][2] -= d
            res += d
            if res == up: break
            self.iter[v] += 1
        return res
 
    def dfs(self, s, t, up):
        stack = [t]
        while stack:
            v = stack[-1]
            if v == s:
                stack.pop()
                flow = up
                for v in stack:
                    to, rev, cap = self.graph[v][self.iter[v]]
                    flow = min(flow, self.graph[to][rev][2])
                for v in stack:
                    self.graph[v][self.iter[v]][2] += flow
                    to, rev, cap = self.graph[v][self.iter[v]]
                    self.graph[to][rev][2] -= flow
                return flow
            lv = self.level[v]
            while self.iter[v] < len(self.graph[v]):
                to, rev, cap = self.graph[v][self.iter[v]]
                if lv <= self.level[to] or self.graph[to][rev][2] == 0:
                    self.iter[v] += 1
                    continue
                stack.append(to)
                break
            if self.iter[v] == len(self.graph[v]):
                stack.pop()
                self.level[v] = self.n
        return 0
 
    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2**63 - 1)
 
    def max_flow_with_limit(self, s, t, limit):
        #assert 0 <= s < self.n
        #assert 0 <= t < self.n
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0: continue
                    self.level[to] = self.level[v] + 1
                    if to == t: break
                    queue.append(to)
            if self.level[t] == -1: break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f: break
                flow += f
        return flow
 
    def min_cut(self, s):
        visited = [0] * self.n
        queue = deque()
        queue.append(s)
        while queue:
            p = queue.popleft()
            visited[p] = True
            for to, rev, cap in self.graph[p]:
                if cap and not visited[to]:
                    visited[to] = True
                    queue.append(to)
        return visited

n = ii()

G = MaxFlow(n + n + 2)
S = 2 * n
T = 2 * n + 1

e = []

for i in range(n):
    G.add_edge(S, i, 1)
    G.add_edge(n + i, T, 1)
for i in range(n):
    u, v = mi()
    e.append(u - 1)
    G.add_edge(u - 1, n + i, 1)
    G.add_edge(v - 1, n + i, 1)

f = G.max_flow(S, T)
ans = [None] * n
for X in G.edges():
    if n <= X[1] < 2 * n and X[3] == 1:
        x = X[1] - n
        if e[x] == X[0]:
            ans[x] = '->'
        else:
            ans[x] = '<-'

for v in ans:
    print(v)
0