logoChat01.ai

Реши задачу(и) с контеста на Python. Требования к...

Tạo vào: 10 tháng 10, 2026

Trả lời bằng GPT-5.6 Thinking bởi Chat01

Câu hỏi

image.png
image.png
image.png

Реши задачу(и) с контеста на Python. Требования к стилю кода:

  • Переменные называй короткими буквами (a, b, c, d, i, j, k, n, m, s, t и т.п.), не словами и не в духе "результат", "количество" — как будто спешащий человек на контесте, а не нейросеть.
  • Комментариев не пиши вообще, даже коротких.
  • Можно небольшие неаккуратности стиля (непоследовательные отступы между блоками, где-то однострочный if, где-то нет, разное именование похожих по смыслу переменных в разных задачах) — но без синтаксических ошибок и без потери читаемости настолько, что код не работает.
  • Не используй докстринги, type hints, избыточную обработку ошибок, f-строки там где обычный print/join достаточен — пиши просто, как в блокноте на контесте.
  • Не добавляй ничего сверх необходимого (без функций-обёрток, если задача не требует, без классов, без argparse и т.д).
    Обязательно перед тем как показать финальный код:
  1. Реши задачу и придумай/выведи формулу или алгоритм сам, не гадай.
  2. Проверь решение брутфорсом или стресс-тестом на случайных данных (небольшие n), сравни с честным перебором, покажи что совпадает.
  3. Прогони через пример(ы) из условия.
  4. Если ограничения большие — проверь производительность на большом тесте (близком к максимальным n/t).
    Дополнительно:
  5. Не бросайся сразу писать код или перебирать варианты руками — сначала явно выпиши структуру задачи (что известно, что нужно доказать), и распланируй шаги вывода формулы/алгоритма.
  6. Если после ~5-7 минут рассуждений нет закрытой формулы или чёткого алгоритма — остановись, покажи текущий прогресс, доказанные промежуточные факты и на чём застрял, вместо того чтобы молча продолжать перебор.
  7. Оцени сложность итогового алгоритма (Big-O по времени и памяти) и явно проверь, что она укладывается в лимиты (n, TL, ML) до того как писать финальный код.
  8. Если задача требует ответ по модулю — используй его только в финальном коде; во время вывода формулы работай с точными числами/логикой, чтобы не запутаться в mod-арифметике раньше времени.
  9. Не переписывай brute-force как единственную проверку по одному случайному тесту — прогони стресс-тест минимум на 100-1000 случайных маленьких кейсов.

Suy nghĩ

Interpreting the game

I’m reading the rules as an ordering game on a tree: two vertices start marked, players alternately mark others, and a point is earned when the chosen vertex has exactly one already-marked neighbor. I’ll derive the optimal score difference.

Interpreted the game

Python

python
from functools import lru_cache
from itertools import combinations
def game(n, edges, x, y):
    adj=[[] for _ in range(n)]
    for a,b in edges:
        adj[a].append(b); adj[b].append(a)
    init=(1<<x)|(1<<y)
    @lru_cache(None)
    def f(mask):
        if mask==(1<<n)-1:return 0
        best=-99
        for v in range(n):
            if not(mask>>v&1):
                c=sum(mask>>u&1 for u in adj[v])
                r=int(c==1)
                best=max(best,r-f(mask|1<<v))
        return best
    return f(init)
def path(n,x,y):
    return game(n,[(i,i+1) for i in range(n-1)],x,y)
for n in range(2,9):
    print('n',n, [[path(n,x,y) for y in range(x+1,n)] for x in range(n-1)])

Python

python
import random, itertools, collections, math
def randtree(n):
    p=[random.randrange(n) for _ in range(n-2)]
    deg=[1]*n
    for z in p:deg[z]+=1
    import heapq
    h=[i for i,d in enumerate(deg) if d==1];heapq.heapify(h)
    e=[]
    for z in p:
        a=heapq.heappop(h); e.append((a,z)); deg[a]-=1;deg[z]-=1
        if deg[z]==1: heapq.heappush(h,z)
    a=heapq.heappop(h);b=heapq.heappop(h);e.append((a,b))
    return e
for n in range(2,10):
    vals=set()
    ex={}
    for _ in range(200):
        e=randtree(n)
        x,y=random.sample(range(n),2)
        g=game(n,e,x,y);vals.add(g);ex[g

Python

python
def state_vals(n,e):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    @lru_cache(None)
    def f(mask):
        if mask==(1<<n)-1:return 0
        return max((int(sum(mask>>u&1 for u in adj[v])==1)-f(mask|1<<v)
                    for v in range(n) if not(mask>>v&1)), default=0)
    d={}
    for mask in range(1<<n):
        d[mask]=f(mask)
    return d
for n in range(2,8):
    e=randtree(n)
    vals=set(state_vals(n,e).values())
    print(n,e,vals)

Suy nghĩ

Tracking components

I’m noticing a useful invariant: the marked vertices form a forest. Choosing a vertex with zero, one, or multiple marked neighbors changes its component count by +1, 0, or a decrease; scoring corresponds exactly to preserving that count.

Tracked components

Python

python
def dist_info(n,e,x,y):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    par=[-1]*n; q=collections.deque([x]); par[x]=x
    while q:
        v=q.popleft()
        if v==y:break
        for u in adj[v]:
            if par[u]<0:par[u]=v;q.append(u)
    path=[];v=y
    while v!=x:path.append(v);v=par[v]
    path.append(x);path=path[::-1]
    return len(path)-1, tuple(len(adj[v]) for v in path), path, adj

for n in range(4,8):
    groups=collections.defaultdict(set)
    for _ in range(1000):
        e=randtree(n); x,y=random.sample(range(n),2)
        d,degs,pa,adj=dist_info(n,e,x,y)
        groups[d].add(game(n,e,x,y))
    print("n",n,{d:s for d,s in groups.items()})

Python

python
for n in [4,5,6]:
    seen={}
    for _ in range(5000):
        e=randtree(n);x,y=random.sample(range(n),2)
        d,degs,pa,adj=dist_info(n,e,x,y)
        if d==2:
            g=game(n,e,x,y)
            if g not in seen:seen[g]=(e,x,y,pa,degs)
            if len(seen)==2:break
    print("n",n,seen)

Python

python
def analyze_state(n,e):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    vals=state_vals(n,e)
    grp=collections.defaultdict(set)
    for mask,v in vals.items():
        z=[i for i in range(n) if mask>>i&1]
        if not z: c=0
        else:
            vis=set();c=0
            for s in z:
                if s in vis:continue
                c+=1;stack=[s];vis.add(s)
                while stack:
                    a=stack.pop()
                    for b in adj[a]:
                        if mask>>b&1 and b not in vis:vis.add(b);stack.append(b)
        m=n-len(z)
        # boundary scoring count
        b=sum(1 for x in range(n) if not(mask>>x&1) and sum(mask>>u&1 for u in adj[x])==1)
        grp[(m%2,c,b)].add(v)
    return grp
e=[(0,3),(1,2),(2,3),(3,4),(4,5)]
grp=analyze_state(6,e)
[(k,v) for k,v in grp.items() if len(v)>1][:20], len(grp)


([((0, 2, 2), {0, 1}), ((1, 2, 1), {0, 1}), ((1, 2, 2), {0, 1})], 21)

Python

python
def local_game_tree(n,e,boundaries): # vertices 0..n-1 unselected, add external selected leaves attached to specified vertices counts maybe
    # boundaries list vertices each ext edge
    N=n+len(boundaries)
    ee=e[:]
    for idx,v in enumerate(boundaries):
        ee.append((v,n+idx))
    adj=[[] for _ in range(N)]
    for a,b in ee:adj[a].append(b);adj[b].append(a)
    init=0
    for i in range(n,N):init|=1<<i
    @lru_cache(None)
    def f(mask):
        if all(mask>>i&1 for i in range(n)): return 0
        return max(int(sum(mask>>u&1 for u in adj[v])==1)-f(mask|1<<v)
                   for v in range(n) if not(mask>>v&1))
    return f(init)
for sz in range(1,8):
    vals1=set(); vals2=set()
    for _ in range(200):
        e=randtree(sz) if sz>1 else []
        vals1.add(local_game_tree(sz,e,[random.randrange(sz)]))
        if sz>=1:
            a,b=random.randrange(sz),random.randrange(sz)
            # two boundary edges, could same vertex
            vals2.add(local_game_tree(sz,e,[a,b]))
    print(sz,vals1, vals2)

Python

python
def path_weights(n,e,x,y):
    d,degs,p,adj=dist_info(n,e,x,y)
    ps=set(p)
    w=[]
    for v in p:
        c=0
        for u in adj[v]:
            if u in ps: continue
            st=[(u,v)]
            while st:
                a,pa=st.pop();c+=1
                for b in adj[a]:
                    if b!=pa:st.append((b,a))
        w.append(c)
    return tuple(w)
for n in range(4,10):
    groups=collections.defaultdict(set)
    for _ in range(5000):
        e=randtree(n);x,y=random.sample(range(n),2)
        key=(dist_info(n,e,x,y)[0],path_weights(n,e,x,y))
        groups[key].add(game(n,e,x,y))
    bad=[(

Python

python
for n in range(4,11):
    groups=collections.defaultdict(set)
    for _ in range(10000):
        e=randtree(n);x,y=random.sample(range(n),2)
        w=path_weights(n,e,x,y)
        key=(len(w), tuple(z%2 for z in w), n%2)
        groups[key].add(game(n,e,x,y))
    bad=[(k,v) for k,v in groups.items() if len(v)>1]
    print(n,"groups",len(groups),"bad",len(bad),bad[:2])

Python

python
def cater(w):
    # path vertices 0..L-1, x=0,y=L-1; attach w_i leaves
    L=len(w); e=[(i,i+1) for i in range(L-1)]
    cur=L
    for i,a in enumerate(w):
        for _ in range(a):
            e.append((i,cur));cur+=1
    return cur,e,0,L-1
for L in range(2,7):
    print("L",L)
    for bits in itertools.product([0,1], repeat=L):
        n,e,x,y=cater(bits)
        g=game(n,e,x,y)
        print(''.join(map(str,bits)),g,end='; ')
    print()

Python

python
def optimal_moves(n,e,x,y):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    init=(1<<x)|(1<<y)
    @lru_cache(None)
    def f(mask):
        if mask==(1<<n)-1:return 0
        return max(int(sum(mask>>u&1 for u in adj[v])==1)-f(mask|1<<v)
                   for v in range(n) if not(mask>>v&1))
    val=f(init); opts=[]
    for v in range(n):
        if not(init>>v&1):
            r=int(sum(init>>u&1 for u in adj[v])==1)
            z=r-f(init|1<<v)
            if z==val:opts.append((v,r,f(init|1<<v)))
    return val,opts
found=0
for n in range(3,10):
  for _ in range(3000):
    e=randtree(n);x,y=random.sample(range(n),2)
    val

Python

python
found=0
for n in range(4,11):
  for _ in range(5000):
    e=randtree(n);x,y=random.sample(range(n),2)
    val,op=optimal_moves(n,e,x,y)
    adj=[[] for _ in range(n)]
    for a,b in e: adj[a].append(b);adj[b].append(a)
    init=(1<<x)|(1<<y)
    has1=any(sum(init>>u&1 for u in adj[v])==1 for v in range(n) if not(init>>v&1))
    if has1 and op and all(r==0 for _,r,_ in op):
        print("only zero",n,val,e,x,y,op)
        found=1;break
  if found:break

Python

python
def check_property(n,e):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    @lru_cache(None)
    def f(mask):
        if mask==(1<<n)-1:return 0
        return max(int(sum(mask>>u&1 for u in adj[v])==1)-f(mask|1<<v)
                   for v in range(n) if not(mask>>v&1))
    for mask in range(1<<n):
        if mask==(1<<n)-1:continue
        sc=[]
        for v in range(n):
            if not mask>>v&1:
                r=int(sum(mask>>u&1 for u in adj[v])==1)
                if r:sc.append(v)
        if sc:
            val=f(mask)
            if all(1-f(mask|1<<v)<val for v in sc):
                return mask,val,sc
    return None

Python

python
for n in range(2,8):
    e=randtree(n); d=state_vals(n,e)
    grp={0:set(),1:set()}
    for mask,v in d.items():
        m=n-mask.bit_count()
        grp[m%2].add(v)
    print(n,e,grp)

Python

python
for n in range(2,9):
    bads=[]
    for _ in range(50):
        e=randtree(n); d=state_vals(n,e)
        for mask,v in d.items():
            if mask and v==-1:
                bads.append((e,mask))
                break
        if bads:break
    print(n, bool(bads), bads[:1])

Python

python
def compare_normal(n,e):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    @lru_cache(None)
    def f(mask):
        if mask==(1<<n)-1:return 0
        return max(int(sum(mask>>u&1 for u in adj[v])==1)-f(mask|1<<v)
                   for v in range(n) if not(mask>>v&1))
    @lru_cache(None)
    def g(mask):
        for v in range(n):
            if not mask>>v&1 and sum(mask>>u&1 for u in adj[v])==1:
                if g(mask|1<<v)==0:return 1
        return 0
    for mask in range(1,1<<n):
        if f(mask)!=g(mask): return mask,f(mask),g(mask)
    return None
for n in range(2,9):
    bad=None
    for _ in range(100):
        e=randtree(n)

Python

python
def formula(n,e,x,y):
    adj=[[] for _ in range(n)]
    for a,b in e: adj[a].append(b);adj[b].append(a)
    par=[-1]*n
    q=collections.deque([x]);par[x]=x
    while q:
        v=q.popleft()
        if v==y:break
        for u in adj[v]:
            if par[u]<0:
                par[u]=v;q.append(u)
    p=[]
    v=y
    while v!=x:
        p.append(v);v=par[v]
    p.append(x);p.reverse()
    on=[False]*n
    for v in p:on[v]=True
    b=[0]*len(p)
    # Count each off-path component size via DFS from neighbors
    for i,v in enumerate(p):
        for u in adj[v]:
            if on[u]:continue
            st=[(u,v)]
            while st:
                a,pa=st.pop(); b[i]^=1  # only parity
                for z in adj[a]:
                    if z!=pa:st.append((z,a))
    if len(p)==2:
        return b[0]^b[1]  # SG 0/1 nonzero
    k=len(p)-2
    dp=[0]*k
    for ln in range(2,k+1):
        nd=[0]*(k-ln+1)
        for ii in range(k-ln+1):
            l=ii+1 # p index
            r=l+ln-1
            a=dp[ii+1] ^ b[l]
            c=dp[ii] ^ b[r]
            if a!=0 and c!=0:
                z=0
            elif a!=1 and c!=1:
                z=1
            else:
                z=2
            nd[ii]=z
        dp=nd
    g=dp[0] if k else 0
    return int((g ^ b[0] ^ b[-1])!=0)

random.seed(1)
bad=[]
for it in range(5000):
    n=random.randint(2,10)
    e=randtree(n)
    x,y=random.sample(range(n),2)
    a=game(n,e,x,y)
    f=formula(n,e,x,y)
    if a!=f:
        bad.append((n,e,x,y,a,f,path_weights(n,e,x,y)))
        break
len(bad),bad[:1]


(0, [])

Python

python
def g_state(n,e,mask):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    @lru_cache(None)
    def g(m):
        for v in range(n):
            if not m>>v&1 and sum(m>>u&1 for u in adj[v])==1:
                if g(m|1<<v)==0:return 1
        return 0
    return g(mask)

def no_score_successors(n,e,mask):
    adj=[[] for _ in range(n)]
    for a,b in e:adj[a].append(b);adj[b].append(a)
    out=[]
    for v in range(n):
        if not mask>>v&1:
            c=sum(mask>>u&1 for u in adj[v])
            if c!=1: out.append((v,c,g_state(n,e,mask|1<<v)))
    return out
for n in range(4,9):
    ex=None
    for _ in range(100):
        e=randtree(n)
        for mask in range(1,(1<<n)-1):
            adj=[[] for _ in range(n)]
            for a,b in e: adj[a].append(b);adj[b].append(a)
            if all(sum(mask>>u&1 for u in adj[v])!=1 for v in range(n) if not mask>>v&1):
                su=no_score_successors(n,e,mask)
                gs=set(z for _,_,z in su)
                if gs=={1}:
                    ex=(e,mask,su);break
        if ex:break
    print(n,ex)

Python

python
for n in range(4,9):
    bad=None
    for _ in range(100):
        e=randtree(n); adj=[[] for _ in range(n)]
        for a,b in e:adj[a].append(b);adj[b].append(a)
        for mask in range(1,(1<<n)-1):
            if any(sum(mask>>u&1 for u in adj[v])==1 for v in range(n) if not mask>>v&1): continue
            for v in range(n):
                if not mask>>v&1 and sum(mask>>u&1 for u in adj[v])>=2:
                    if g_state(n,e,mask|1<<v)!=0:
                        bad=(e,mask,v,sum(mask>>u&1 for u in adj[v]));break
            if bad:break
        if bad:break
    print(n,bad)

Python

python
for sz in range(1,9):
    vals=set()
    for _ in range(200):
        e=randtree(sz) if sz>1 else []
        vals.add(local_game_tree(sz,e,[0,0]))
    print(sz,vals)

Python

python
sample='''4
3 1 2
1 2
2 3
4 1 4
1 2
2 3
3 4
3 1 3
1 2
2 3
6 2 3
1 2
1 3
1 4
1 5
1 6
'''
def solve_data(s):
    it=iter(map(int,s.split()))
    t=next(it);out=[]
    for _ in range(t):
        n=next(it);x=next(it)-1;y=next(it)-1
        e=[]
        for i in range(n-1):
            a=next(it)-1;b=next(it)-1;e.append((a,b))
        out.append(formula(n,e,x,y))
    return out
solve_data(sample)


[1, 1, 0, 0]

Python

python
code = r'''
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n,x,y=map(int,input().split())
    x-=1
    y-=1
    a=[[] for _ in range(n)]
    for i in range(n-1):
        u,v=map(int,input().split())
        u-=1
        v-=1
        a[u].append(v)
        a[v].append(u)

    q=[x]
    p=[-1]*n
    p[x]=x
    for v in q:
        if v==y: break
        for u in a[v]:
            if p[u]==-1:
                p[u]=v
                q.append(u)

    c=[]
    v=y
    while v!=x:
        c.append(v)
        v=p[v]
    c.append(x)
    c.reverse()

    z=[0]*n
    for v in c:
       

'1\n1\n0\n0\n'

Python

python
import time
n=3000
e=[(i,i+1) for i in range(n-1)]
st=time.perf_counter()
r=formula(n,e,0,n-1)
elapsed=time.perf_counter()-st
elapsed,r


(0.8746384730000045, 1)

Python

python
# exhaustive all labeled trees up to n=6, all x<y
import heapq, itertools, time, math

def tree_from_prufer(p):
    n=len(p)+2
    deg=[1]*n
    for x in p: deg[x]+=1
    h=[i for i in range(n) if deg[i]==1]; heapq.heapify(h)
    e=[]
    for x in p:
        u=heapq.heappop(h);e.append((u,x))
        deg[u]-=1;deg[x]-=1
        if deg[x]==1:heapq.heappush(h,x)
    e.append((heapq.heappop(h),heapq.heappop(h)))
    return e

st=time.perf_counter()
cnt=0
bad=None
for n in range(2,7):
    seqs=[()] if n==2 else itertools.product(range(n), repeat=n-2)
    for pseq in seqs:
        e=tree_from_prufer(pseq)
        for x in range(n):
            for y in range(x+1,n):
                cnt+=1
                if game(n,e

(0.608857629000056, 20796, None)



(4495501, 4492503)

Suy nghĩ

Designed and validated a tree-game solver through parity analysis and testing

Worked for 8m 15s

Trả lời

Сначала разложим задачу по структуре, а потом уже код.

1. Что здесь на самом деле нужно посчитать

Пусть текущее множество вершин со значением 0 — это SS.

Ход в вершину vv приносит очко тогда и только тогда, когда у vv ровно один сосед уже лежит в SS.

Полезная лемма для дерева:

Если хотя бы одна вершина уже равна 0, то значение оставшейся игры для игрока, который сейчас ходит, всегда равно либо 0, либо 1.
Если существует ход, приносящий очко, оптимальный ход можно выбирать только среди таких ходов. Если ходов на очко нет, значение позиции равно 0.

Это доказывается индукцией по числу оставшихся единиц. Для хода с очком переход имеет вид 1−F′1-F', для хода без очка — −F′-F'; после индукционного шага F′∈{0,1}F'\in\{0,1\}, поэтому нулевой ход не может быть лучше очкового. В случае отсутствия очковых ходов ацикличность дерева позволяет тем же удалением крайних компонент получить значение 0.

Следовательно, исходную игру можно заменить на обычную impartial game:

  • разрешены только вершины с ровно одним нулевым соседом;
  • кто не может сделать такой ход — проиграл.

Если эта вспомогательная игра выигрышная для первого игрока, исходное p−q=1p-q=1, иначе p−q=0p-q=0.

То есть ответ здесь всегда только 0 или 1.

2. Что происходит на пути между xx и yy

Рассмотрим единственный путь

v0=x,v1,…,vk=y.v_0=x,v_1,\ldots,v_k=y.

Во вспомогательной игре нулевые вершины растут двумя связными областями: от xx и от yy.

Вне пути никаких конфликтов быть не может: если ветка уже прикреплена к нулевой вершине пути, её можно целиком постепенно закрасить.

А на самом пути области идут навстречу друг другу. В конце останется ровно одна вершина пути, которую взять нельзя: у неё окажутся сразу два нулевых соседа.

Для каждой viv_i обозначим через bib_i число вершин во всех ветках, отходящих от неё не по пути.

Нам нужна только чётность bib_i.

Почему: игра в такой подвешенной ветке всегда длится ровно столько ходов, сколько в ней вершин. Поэтому её число Шпрага—Гранди:

bi mod 2.b_i\bmod 2.

3. DP по оставшемуся отрезку пути

Пусть

G(l,r)G(l,r)

— число Шпрага—Гранди игры, когда между двумя уже занятыми областями остались вершины пути vl,…,vrv_l,\ldots,v_r.

Если l=rl=r, единственная вершина уже имеет двух нулевых соседей, поэтому:

G(l,l)=0.G(l,l)=0.

Если l<rl<r, можно взять либо левый, либо правый конец.

После взятия vlv_l:

  • остаётся G(l+1,r)G(l+1,r);
  • активируются боковые ветки vlv_l, их SG равен bl mod 2b_l\bmod2.

Значит первый вариант:

G(l+1,r)⊕(bl mod 2).G(l+1,r)\oplus (b_l\bmod2).

Аналогично справа:

G(l,r−1)⊕(br mod 2).G(l,r-1)\oplus (b_r\bmod2).

Поэтому

G(l,r)=mex⁡(G(l+1,r)⊕bl,  G(l,r−1)⊕br),G(l,r)=\operatorname{mex}\left( G(l+1,r)\oplus b_l,\; G(l,r-1)\oplus b_r \right),

где в b сразу храним только чётности.

У xx и yy боковые ветки активны изначально, поэтому итоговый SG:

G(1,k−1)⊕b0⊕bk.G(1,k-1)\oplus b_0\oplus b_k.

Если он ненулевой — ответ 1, иначе 0.

DP зависит только от предыдущей диагонали, поэтому память O(n)O(n).

4. Проверка брутфорсом

Для честного перебора маленьких деревьев я использовал состояние mask нулевых вершин и точный minimax:

F(mask)=max⁡v([cv=1]−F(mask∪{v})).F(mask)= \max_v \left( [c_v=1]-F(mask\cup\{v\}) \right).

Проверки:

  • перебраны все помеченные деревья до n=6n=6 и все пары x,yx,y: 20796 позиций, расхождений 0;
  • ещё 5000 случайных деревьев с 2≤n≤102\le n\le10: 5000/5000 совпадений с полным minimax.

Для примера из условия алгоритм получил:

text
1
1
0
0

что полностью совпадает.

5. Сложность

Путь и размеры подвешенных частей находятся за O(n)O(n).

Интервальный DP:

O(d2)≤O(n2),O(d^2)\le O(n^2),

где dd — длина пути между xx и yy.

Память:

O(n).O(n).

При n=3000n=3000 в худшем случае получается примерно 4.5 млн DP-переходов. На тесте-пути из 3000 вершин вычисление заняло около 0.9 с в текущем окружении. При лимите 2 с, сумме n≤3000n\le3000 и памяти 256 МБ укладывается.

Код

python
import sys

it=iter(map(int,sys.stdin.buffer.read().split()))
t=next(it)
o=[]

for _ in range(t):
    n=next(it)
    x=next(it)-1
    y=next(it)-1

    a=[[] for _ in range(n)]
    for i in range(n-1):
        u=next(it)-1
        v=next(it)-1
        a[u].append(v)
        a[v].append(u)

    p=[-1]*n
    p[x]=x
    q=[x]
    for v in q:
        if v==y:
            break
        for u in a[v]:
            if p[u]==-1:
                p[u]=v
                q.append(u)

    c=[]
    v=y
    while v!=x:
        c.append(v)
        v=p[v]
    c.append(x)
    c.reverse()

    z=[0]*n
    for v in c:
        z[v]=1

    b=[0]*len(c)
    for i,v in enumerate(c):
        for u in a[v]:
            if z[u]:
                continue
            s=[(u,v)]
            while s:
                w,pa=s.pop()
                b[i]^=1
                for h in a[w]:
                    if h!=pa:
                        s.append((h,w))

    m=len(c)-2

    if m<=1:
        g=0
    else:
        d=[0]*m

        for k in range(2,m+1):
            e=[0]*(m-k+1)

            for i in range(m-k+1):
                l=i+1
                r=i+k

                u=d[i+1]^b[l]
                v=d[i]^b[r]

                if u and v:
                    w=0
                elif u!=1 and v!=1:
                    w=1
                else:
                    w=2

                e[i]=w

            d=e

        g=d[0]

    o.append(str(int((g^b[0]^b[-1])!=0)))

sys.stdout.write('\n'.join(o))

Chia sẻ Q&A này