結果
問題 | No.1914 Directed by Two Sequences |
ユーザー |
|
提出日時 | 2022-02-06 23:11:19 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,600 bytes |
コンパイル時間 | 438 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 114,220 KB |
最終ジャッジ日時 | 2024-12-16 01:35:51 |
合計ジャッジ時間 | 15,677 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 RE * 28 |
ソースコード
def solve(N,A,B,M,E):A = [a-1 for a in A]B = [b-1 for b in B]res = set()edge = [set() for v in range(N)]for u,v in E:edge[u-1].add(v-1)edge[v-1].add(u-1)group = [-1 for v in range(N)]for v in range(N):mex = [False for i in range(len(edge[v])+1)]for nv in edge[v]:if nv < v and group[nv] < len(mex):mex[group[nv]] = Truefor i in range(len(mex)):if not mex[i]:group[v] = ibreakn = max(group) + 1clique = [[] for g in range(n)]for v in range(N):clique[group[v]].append(v)def direct(i,j):if i < j:return A[i] < B[j]else:return B[i] < A[j]def hamilton_path(V):n = len(V)if n <= 1:return VA = hamilton_path(V[:n//2])B = hamilton_path(V[n//2:])res = []bi = 0for ai in range(len(A)):while bi<len(B) and direct(B[bi],A[ai]):res.append(B[bi])bi += 1res.append(A[ai])res += B[bi:]return residx = [-1 for v in range(N)]for g in range(n):clique[g] = hamilton_path(clique[g])for i in range(len(clique[g])):idx[clique[g][i]] = ifor u,v in zip(clique[g],clique[g][1:]):res.add((u,v))memo_to = [N for v in range(N)]memo_from = [-1 for v in range(N)]ci = [i for i in range(n)]ci.sort(lambda g:len(clique[g]))Vs = []for i in range(n):target = ci[i]Vs += clique[target]for v in Vs:for nv in clique[target]:if v==nv:continueif direct(v,nv) and nv not in edge[v]:memo_to[v] = min(memo_to[v],idx[nv])if direct(nv,v) and v not in edge[nv]:memo_from[v] = max(memo_from[v],idx[nv])if memo_to[v]!=N:nv = clique[target][memo_to[v]]res.add((v,nv))memo_to[v] = Nif memo_from[v]!=-1:pv = clique[target][memo_from[v]]res.add((pv,v))memo_from[v] = -1print(len(res))for u,v in res:print(u+1,v+1)import sysinput = lambda :sys.stdin.buffer.readline()mi = lambda :map(int,input().split())li = lambda :list(mi())N,M = mi()assert N<= 5000A = li()B = li()E = [tuple(mi()) for i in range(M)]solve(N,A,B,M,E)