Submission #1159907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159907		ach00	Drivers (BOI24_drivers)	Pypy 3	100 / 100	1298 ms	124696 KiB

Main

n,m,q = map(int, input().split())


PT = []
SZ = []
for i in range(n):
    SZ.append(1)
    PT.append(i)

def find(u):
    if(PT[u] != u): PT[u] = find(PT[u])
    return PT[u]

def unite(u, v):
    u = find(u)
    v = find(v)
    if(u == v): return
    if(SZ[u] > SZ[v]): u,v = v,u
    SZ[v] += SZ[u]
    PT[u] = v


edges = []

for i in range(m):
    a,b,t = map(int,input().split())
    a -= 1
    b -= 1
    edges.append((t,a,b))
edges = sorted(edges)

queries = []
cur_edge = 0
for i in range(q):
    a,b,p = map(int,input().split())
    a -= 1
    b -= 1
    queries.append((p,i,a,b))

queries = sorted(queries)
ans = [0] * q
for i in range(q):
    a = queries[i][2]
    b = queries[i][3]
    p = queries[i][0]
    while(cur_edge < m and edges[cur_edge][0] <= p):
        unite(edges[cur_edge][1], edges[cur_edge][2])
        cur_edge += 1
    if(find(a) == find(b)):
        ans[queries[i][1]] = 1
    else:
        ans[queries[i][1]] = 0

for i in range(q):
    if(ans[i]):
        print("TAIP")
    else:
        print("NE")

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 40%)

=======

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45