Submission #1159908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159908		madshoff	Drivers (BOI24_drivers)	Pypy 3	0 / 100	135 ms	48808 KiB

Main

from heapq import*
n,m,u = list(map(int,input().split()))

cities = [(_,-1) for _ in range(n)]
groups = [[_] for _ in range(n)]
roads = []
for i in range(m):
    x,y,t = list(map(int,input().split()))
    roads.append((t,x-1,y-1))
roads.sort()
roads.append((10**9+7,x-1,y-1))
roads.reverse()
#print("roads:",roads)
#print("citites:",cities)

queries = []
for q in range(u):
    a,b,t = list(map(int,input().split()))
    queries.append((t,a-1,b-1,q))
queries.sort()


final = ["NE"]*u

last_road = roads.pop()

for query in queries:
    limit = query[0]
    x = query[1]
    y = query[2]

    while last_road[0]<=limit:
        if cities[y][1] != cities[x][1]:
            if len(groups[cities[y][1]])>=len(groups[cities[x][1]]):
                groups[y] = groups[y-1]+groups[x]
                cities[groups[x][0]] = (groups[x][0],groups[y][0])
            
            else:
                groups[x] = groups[x]+groups[y]
                cities[groups[y][0]] = (groups[y][0],groups[x][0])
        
        
        elif cities[y][1]==-1:
            groups[y] = groups[y]+groups[x]
            cities[groups[x][0]] = (groups[x][0],groups[y][0])
            cities[y] = (y,y)
        
        
        last_road= roads.pop()
    if cities[x][1] == cities[y][1] and cities[x][1]!=-1:
        final[query[3]] = "TAIP"


#print(adj)
#print(groups)
#print(cities)
print("\n".join(final))
#for road in adj:
#    a = adj

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

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