TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:    1. Throw the die. The current score is the result of the die.   2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.   3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.  You are given N and K. Find the probability that Snuke wins the game.

Submission attempts (in order):
import decimal

N, K = map(int, input().split())
n = decimal.Decimal(N)
result = decimal.Decimal(0.00000000000)

def check(i, K):
    count = 0
    while (K > i):
        i *= 2
        count += 1
    return count

for i in range(1,N+1):
    count = check(i, K)
    dec = decimal.Decimal(1.00000000000)
    for j in range(count):
        dec /= decimal.Decimal(2.00000000000)
    result += dec

print(result/n)

N, K = map(int, input().split())
result = 0

def check(i, K):
    count = 0
    while (K > i):
        i *= 2
        count += 1
    return count

for i in range(1,N+1):
    count = check(i, K)
    dec = 1
    for j in range(count):
        dec /= 2.0
    result += dec

print(round(result/N, 12))

Verdicts: Time Limit Exceeded

Accepted
Problem: Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:    1. Throw the die. The current score is the result of the die.   2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.   3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.  You are given N and K. Find the probability that Snuke wins the game.

Submission attempts (in order):
import math
N,K = map(int,input().split())


print(sum([(1/N)*(0.5)**math.ceil(math.log2(max(K//i,1))) for i in range(1,N+1)])

import math
N,K = map(int,input().split())


print(sum([(1/N)*(0.5)**math.ceil(math.log2(max(K//i,1))) for i in range(1,N+1)]))

import math
N,K = map(int,input().split())


print(sum([(1/N)*(0.5)**math.ceil(math.log2(max(K//i,1))) for i in range(1,N+1)])

import math
N,K = map(int,input().split())


print(sum([(1/N)*(0.5)**math.ceil(math.log2(math.ceil(K/i))) if i<K else 1/N for i in range(1,N+1)])

import math
N,K = map(int,input().split())


print('{:.12f}'.format(sum([(1/N)*(0.5)**math.ceil(math.log2(math.ceil(K/i))) if i<K else 1/N for i in range(1,N+1)])))

Verdicts: Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Accepted
Problem: Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:    1. Throw the die. The current score is the result of the die.   2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.   3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.  You are given N and K. Find the probability that Snuke wins the game.

Submission attempts (in order):
N, K = map(int, input().split())

cnt = 0
while 2 ** cnt < K:
    cnt += 1

print(cnt)
res = 0
for i in range(1, N + 1):
    while i * (2 ** cnt) >= K and cnt >= 0:
        cnt -= 1
    cnt += 1
    res += 1 / ((2 ** cnt) * N)

print("{:.12g}".format(res))


N, K = map(int, input().split())

cnt = 0
while 2 ** cnt < K:
    cnt += 1

print(cnt)
res = 0
for i in range(1, N + 1):
    while i * (2 ** cnt) >= K and cnt >= 0:
        cnt -= 1
    cnt += 1
    res += 1 / ((2 ** cnt) * N)

print(res)


N, K = map(int, input().split())

cnt = 0
while 2 ** cnt < K:
    cnt += 1

res = 0
for i in range(1, N + 1):
    while i * (2 ** cnt) >= K and cnt >= 0:
        cnt -= 1
    cnt += 1
    res += 1 / ((2 ** cnt) * N)

print("{:.12g}".format(res))


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:    1. Throw the die. The current score is the result of the die.   2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.   3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.  You are given N and K. Find the probability that Snuke wins the game.

Submission attempts (in order):
from fractions import Fraction

N, K = map(int, input().split())


def saikoro(x):
    y = Fraction(1, N)
    kakuritu = 1
    while 1 <= x and x <= K - 1:
        
        x *= 2
        kakuritu *= 0.5
        if (x <= K):
            continue
        elif (x >= K):
            return kakuritu * float(y)
            break


count = 0
for i in range(1, N + 1):
    count += saikoro(i)
print(count)


from fractions import Fraction

N, K = map(int, input().split())

y = Fraction(1, N)


count = 0
for i in range(1, N + 1):
    kakuritu = 1
    while 1 <= i and i <= K - 1:
        i *= 2
        kakuritu /= 2
        if (i <= K):
            continue
        elif (i >= K):
            break
    count += kakuritu
print("{:.12f}".format(count * float(y)))


Verdicts: Runtime Error

Accepted
Problem: Snuke has a fair N-sided die that shows the integers from 1 to N with equal probability and a fair coin. He will play the following game with them:    1. Throw the die. The current score is the result of the die.   2. As long as the score is between 1 and K-1 (inclusive), keep flipping the coin. The score is doubled each time the coin lands heads up, and the score becomes 0 if the coin lands tails up.   3. The game ends when the score becomes 0 or becomes K or above. Snuke wins if the score is K or above, and loses if the score is 0.  You are given N and K. Find the probability that Snuke wins the game.

Submission attempts (in order):
def d_even_relation_bfs():
    from collections import deque
    N = int(input())
    Edges = [[int(i) - 1 for i in input().split()] for j in range(N - 1)]  # 0-indexed

    graph = [[] for _ in range(N)]
    for u, v, w in Edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    distance_from_root = [0] * N  

    queue = deque([(-1, 0, 0)])  
    while queue:
        parent, current, distance = queue.pop()
        distance_from_root[current] = distance
        for next_vertex, dist in graph[current]:
            if parent != next_vertex:  
                queue.appendleft((current, next_vertex, distance + dist))
    ans = (1 if d % 2 == 0 else 0 for d in distance_from_root)
    return ' '.join(map(str, ans))

print(d_even_relation_bfs())

def c_dice_and_coin():
    from math import ceil, log2
    N, K = [int(i) for i in input().split()]

    ans = 1 / N * sum(1 / 2**max(ceil(log2(K / d)), 0) for d in range(1, N + 1))
    return round(ans, 12)

print(c_dice_and_coin())

Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))


import sys
sys.setrecursionlimit(200000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))


Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
N, M = [int(i) for i in input().strip().split(' ')]

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  if key in a:
    for k in a[key]:
      make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

N, M = [int(i) for i in input().strip().split(' ')]

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  for k in a[key]:
    make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

N, M = [int(i) for i in input().strip().split(' ')]

a = {}
for i in range(M):
  X, Y, _ = [int(i) for i in input().strip().split(' ')]
  if X not in a: a[X] = set()
  if Y not in a: a[Y] = set()
  a[X].add(Y)
  a[Y].add(X)

len_a = len(a)


def test(key_set):
  tmp = set()
  for key in key_set:
    if key in a:
      tmp = tmp.union(a[key])
      del a[key]

  #print('key_set = {}, tmp = {}'.format(key_set, tmp))
  return tmp


counter = 0
# print(b)

while len(a) > 0:
  #print('---')
  #print('a = {}'.format(a))
  key, key_set = a.popitem()
  #print('key = {}, key_set = {}'.format(key, key_set))
  tmp = test(key_set)
  while len(tmp) > 0:
    tmp = test(tmp)
  #print('a = {}'.format(a))
  counter += 1

print(counter + N - len_a)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def search(x, y):
            tmp = [y]
            curr = x
            while curr != -1:
                tmp.append(curr)
                curr = t[curr]
            root = tmp.pop()
            for _t in tmp:
                t[_t] = root

        search(x, y)
    return str(t[1:].count(-1))


if __name__ == '__main__':
    print(solve(input()))


def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)

    def union(r1, r2):
        if r1 != r2:
            t[max(r1, r2)] = min(r1, r2)

    def find(x):
        if t[x] < 0:
            return x
        t[x] = find(t[x])
        return t[x]

    for x, y, _ in zip(*[iter(xyz)] * 3):
        union(find(x), find(y))
    return str(t.count(-1) - 1)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))


Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(1, N + 1):
    if visited[i]:
        continue
    ans += 1
    dfs(i)
print(ans)

N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(N):
    if visited[i]:
        continue
    ans += 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in t[s]:
            if visited[to]:
                continue
            visited[to] = 1
            stack.append(to)
print(ans)

Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
n, m = map(int, input().split())
datalist = [0 for i in range(n)]
ans = 0
root = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    root[x - 1].append(y - 1)
    root[y - 1].append(x - 1)

def solve(now):
    global ans, root
    for j in range(len(root[now])):
        if not datalist[root[now][j]]:
            datalist[root[now][j]] = 1
            solve(root[now][j])

for i in range(n):
    if not datalist[i]:
        solve(i)
        ans += 1

for i in datalist:
    if i == 0:
        ans += 1
        datalist[i] = 1
        solve(i)

print(ans)

n, m = map(int, input().split())
datalist = [0 for i in range(n)]
ans = 0
root = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    root[x - 1].append(y - 1)
    root[y - 1].append(x - 1)

def solve(now):
    global ans, root
    for j in range(len(root[now])):
        if not datalist[root[now][j]]:
            datalist[root[now][j]] = 1
            solve(root[now][j])

for i in range(n):
    if not datalist[i]:
        solve(i)
        ans += 1

for i in datalist:
    if i == 0:
        ans += 1
        datalist[i] = 1
        solve(i)

print(ans)

import sys
sys.setrecursionlimit(10000000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[tree[now][i]]:
            visit_tree(tree[now][i], num)

n, m = map(int, input().split())
tree = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    tree[x - 1].append(y - 1)
    tree[y - 1].append(x - 1)

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Verdicts: Runtime Error

Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
n,m=map(int,input().split())
    
root=[int(i) for i in range(n)] 
rank=[0]*n    
def find(x):
    if root[x]==x:
        return x 
    else:
        return find(root[x])

for i in range(m):
    x,y,z=map(int,input().split())
    fx=find(x-1)
    fy=find(y-1)
    if rank[fx]>=rank[fy]:
        root[fy]=fx
        if rank[fx]==rank[fy]:
            rank[fx]+=1
    else:
        root[fx]=fy 
a=()
for i in range(n):
    a.add(find(i)) 
print(len(a))

n,m=map(int,input().split())
    
root=[int(i) for i in range(n)] 
rank=[0]*n    
def find(x):
    if root[x]==x:
        return x 
    else:
        return find(root[x])

for i in range(m):
    x,y,z=map(int,input().split())
    fx=find(x-1)
    fy=find(y-1)
    if rank[fx]>=rank[fy]:
        root[fy]=fx
        if rank[fx]==rank[fy]:
            rank[fx]+=1
    else:
        root[fx]=fy 
a=[]
for i in range(n):
    a.append(find(i)) 
print(len(set(a)))

Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
K = 1

class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
            return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)
    
u = UnionFind(N)
for a, b, _ in L:
    u.unite(a, b)
    
exit()
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)
    
u = UnionFind(N)
for a, b, _ in L:
    u.unite(a, b)
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
f-8

N, M = (int(x) for x in input().split())

adj_list = [[] for i in range(N)]
for i in range(M):
	x, y, z = (int(x) for x in input().split())
	adj_list[x - 1].append(y - 1)
	adj_list[y - 1].append(x - 1)

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	while len(stack) > 0:
		node = stack.pop()
		searched[node] = True
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)

print(count)

# coding: utf-8

N, M = (int(x) for x in input().split())

adj_list = [[] for i in range(N)]
for i in range(M):
	x, y, z = (int(x) for x in input().split())
	adj_list[x - 1].append(y - 1)
	adj_list[y - 1].append(x - 1)

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	searched[i] = True
	while len(stack) > 0:
		node = stack.pop()	
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)
				searched[n] = True

print(count)

Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        X, Y, Z = map(int, input().split())
        uf.union(X-1, Y-1)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()


import sys

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        X, Y, Z = map(int, input().split())
        uf.union(X-1, Y-1)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()


Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
N,M=map(int,input().split())
root=[-1]*N
def search(i):
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
for i in range(M):
    x,y,z=map(int,input().split())
    x-=1
    y-=1
    rx=search(x)
    ry=search(y)
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[ry]+=root[rx]
        root[rx]=ry
    else:
        root[rx]+=root[ry]
        root[ry]=rx
ans=0
print(root)
for i in range(N):
    if root[i]<0:
        ans+=1
print(ans)

N,M=map(int,input().split())
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(M):
    X,Y,Z=map(int,input().split())
    rx=find(X-1)
    ry=find(Y-1)
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
    elif root[rx]>root[ry]:
        root[ry]+=root[rx]
        root[rx]=ry
ans=0
for r in root:
    if r<0:
        ans+=1
print(ans)

Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
n, m = map(int, input().split())

xy = [0 for _ in range(n + 1)]

for _ in range(m):
    x, y, z = map(int, input().split())
    if xy[y] == 0:
        xy[y] = x
    elif xy[x] == 0:
        xy[x] = y

ans = 0
for i in xy:
    if i == 0:
        ans += 1

print(ans)


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

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y = map(int, input().split()[:2])
    xy[root(x)] = root(y)

print(sum(i == v for i, v in enumerate(xy)) - 1)


Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def samegrp(self, x, y):
        return self.root(x) == self.root(y)

from mymodules.somedatastrs import UnionFind

n, m = [int(x) for x in input().split()]
A = UnionFind(n)
ans = n
for i in range(m):
    x, y, _ = [int(z) - 1 for z in input().split()]
    if not A.samegrp(x, y):
        ans -=1
    A.union(x, y)

print(ans)

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def samegrp(self, x, y):
        return self.root(x) == self.root(y)

n, m = [int(x) for x in input().split()]
A = UnionFind(n)
ans = n
for i in range(m):
    x, y, _ = [int(z) - 1 for z in input().split()]
    if not A.samegrp(x, y):
        ans -=1
    A.union(x, y)

print(ans)


Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
import copy

N, M = map(int, input().split())


rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	rule_list[i][0] -= 1
	rule_list[i][1] -= 1
	のZを0,1にする。
	rule_list[i][2] = (rule_list[i][2] % 2)


check_list = [-1 for i in range(N)]


hints = 1


check_list[0] = 1


while(True):
	をチェック
	
	for i, rule in enumerate(rule_list):
		if(check_list[rule[0]] != -1):
			check_list[rule[1]] = (check_list[rule[0]] + check_list[rule[2]]) % 2
		elif(check_list[rule[1]] != -1):
			check_list[rule[0]] = (check_list[rule[1]] + check_list[rule[2]]) % 2
		else:
			pass
	
	try:
		tmp_chk = check_list.index(-1)
		hints += 1
		
		check_list[tmp_chk] = 1

	
	except ValueError:
		break

print(hints)

class UnionTree:

	
	def __init__(self, N):
		self.__par = [i for i in range(N)]
		self.__rank = [0] * N

	
	def root(self, x):
		if(self.__par[x] == x):
			return x
		else:
			self.__par[x] = self.root(self.__par[x])
			return self.__par[x]

	
	def unite(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if(rx == ry):
			return

		if(self.__rank[rx] < self.__rank[ry]):
			self.__par[rx] = ry
		else:
			self.__par[ry] = rx
			if(self.__rank[rx] == self.__rank[ry]):
				self.__rank[rx] += 1

	
	def same(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if(rx == ry):
			return True
		
		

N, M = map(int, input().split())

# UnionTree Class
union_tree = UnionTree(N)


for i in range(M):
	
	a, b, x = map(int, input().split())
	union_tree.unite(a-1, b-1)


cnt = set()

for i in range(N):
	cnt.add(union_tree.root(i))

print(len(cnt))

Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):

n, m = list(map(int, input().split()))
dic = {}  
count = 0
for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a in dic:
    dic[a]=[b]
  else:
    dic[a].append(b)

dp = [0]*n
print(dic)
for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
  else:
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
#print(dp)
print(count)

import queue

n, m = list(map(int, input().split()))
dic = {}  
count = 0
q = queue.Queue()

for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a-1 in dic:
    dic[a-1]=[b-1]
  else:
    dic[a-1].append(b-1)
  
  if not b-1 in dic:
    dic[b-1]=[a-1]
  else:
    dic[b-1].append(a-1)

dp = [0]*n

#print(dic)

for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i in dic:
      for j in dic[i]:
        dp[j]=count
        q.put(j)
    #print(dp)
    while not q.empty():
      temp = q.get()
      #print(temp)
      if temp in dic:
        for j in dic[temp]:
          if dp[j] == 0:
            dp[j]=count
            q.put(j)
#print(dp)
print(count)

Verdicts: Wrong Answer

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
import sys


sys.setrecursionlimit(10 ** 100)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]



graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)


from sys import setrecursionlimit


setrecursionlimit(10 ** 100)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]



graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)


import sys


sys.setrecursionlimit(10 ** 20)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]



graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)


import sys



sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]



graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.root = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.root[a] == a:
            return a
        else:
            self.root[a] = self.root(self.root[a])
            return self.root[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.root[ra] = rb
        else:
            self.root[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y,z in src:
    x,y = x-1,y-1
    uf.unite(x,y)
print(N - uf.count)


def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

def same(x,y):
    return find(x) == find(y)

def unite(x,y):
    x = find(x)
    y = find(y)
    if rank[x] == rank[y]:
        root[y] = x
        rank[x] += 1
    elif rank[x] > rank[y]:
        root[y] = x
    elif rank[x] < rank[y]:
        root[x] = y
    
n,m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(m):
    x, y, z = [int(i)-1 for i in input().split()]
    if not same(x,y):
        unite(x,y)
    
for i in range(n):
    find(i)

print(len(list(set(root))))


Verdicts: Runtime Error

Accepted
Problem: There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i-th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:    * For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.  You are a magician and can use the following magic any number of times:  **Magic** : Choose one card and know the integer A_i written on it. The cost of using this magic is 1.  What is the minimum cost required to determine all of A_1, A_2, ..., A_N?  It is guaranteed that there is no contradiction in given input.

Submission attempts (in order):
import sys
input = sys.stdin.readline

N,M = [int(i) for i in input().split()]
l = [[] for _ in range(N)]
ans = set()
for i in range(M):
    x,y,_ = [int(j)-1 for j in input().split()]
    while len(l[x]) != 0:
        x = l[x][0]
    ans.add(x)
    l[y].append(x)

print(len(ans))


import sys
sys.setrecursionlimit(20000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry

N,M = [int(i) for i in input().split()]
uf = UnionFind(N)

for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)

ans = set()
for i in range(N):
    ans.add(uf.root(i))
print(uf.par)
print(len(ans))


import sys
sys.setrecursionlimit(200000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]

    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry

    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry

N,M = [int(i) for i in input().split()]
uf = UnionFind(N)

for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)

ans = set()
for i in range(N):
    ans.add(uf.root(i))
print(len(ans))


Verdicts: Wrong Answer

Runtime Error

Accepted