Blog entries - Codeforces

ammar007's blog

IEEExtreme 19.0 Training Sessions Solutions

By ammar007, history, 6 months ago, In English

Mosaic Decoration I

Python Solution

from math import ceil
n, cb, cp = map(int, input().split())
bt, pt = 0, 0
for i in range(n):
    b, p = map(int, input().split())
    bt += b
    pt += p

result = cb * ceil(bt/10) + cp * ceil(pt/10)
print(result)

Stick

Python Solution

n, k, l = map(int, input().split())

w = l*2
a = w**2

if k >= w:
    print(a*n)
else:
    b = a - (w-k)**2
    print(a + (n-1) * b)

Restaurant Cipher

Python Solution

n = int(input())

for i in range(n):
    f = {j: 0 for j in "ABCDEFG"}
    line = input()
    for j in line.upper():
        if j in f:
            f[j] += 1
    
    print(max(f.items(), key=lambda x: x[1])[0])

Laser Defense

Python Solution

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

off = {'L': 0, 'U': l, 'R': l*2}
arr = []
for i in range(n):
    s, p = input().split()
    arr.append((off[s] + int(p), 'A'))
for i in range(m):
    s, p = input().split()
    arr.append((off[s] + int(p), 'B'))
    
arr.sort()

result = 1
prev_b = 0
for i, t in arr:
    if t == 'B':
        result += 1
        prev_b += 1
    else:
        result += prev_b + 1
print(result)

Full text and comments »

ammar007
6 months ago
0

TCPC 2022 Solutions

By ammar007, history, 20 months ago, In English

A. Mood

Python Solution

def read():
    return int(input())

def read_list():
    return [int(i) for i in input().split()]


def solve():
    x, y = read_list()
    print(max(0, y-x))

for i in range(read()):
    solve()

B. Hungry

Python Solution

def read():
    return int(input())

def read_list():
    return [int(i) for i in input().split()]

def solve():
    n = read()
    a = read_list()
    prefix_sum = [0]*(n+1)
    for i in range(1, n+1):
        prefix_sum[i] = prefix_sum[i-1] + a[i-1]
    q = read()
    for i in range(q):
        x, y, m = read_list()
        result = min(max(x, prefix_sum[n]), prefix_sum[m]+y)
        print(result)


solve()

C. Ice Coffee

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]


max_a = int(1e7)
nxt = [1] * (max_a+1)

# modified sieve of eratosthenes
for i in range(2, max_a+1):
    if nxt[i] == 1:
        for j in range(i*i, max_a+1, i):
            if nxt[j] == 1:
                nxt[j] = j//i


def solve():
    n = read()
    a = read_list()
    b = read_list()
    result = 0
    for i in range(n):
        x = a[i]
        y = b[i]
        while x != y:
            if x > y:
                x = nxt[x]
            else:
                y = nxt[y]
            result += 1
    print(result)

for i in range(read()):
    solve()

D. Beautiful decrease

Python Solution


def read():
    return int(input())

def read_list():
    return [int(i) for i in input().split()]


def solve():
    n, q = read_list()
    a = read_list()
    total = sum(a)
    b_decreases = [] # (length, k)

    # monotonic stack
    stack = [(0, -1)]
    

    def mono_push(value, index):
        if value > stack[-1][0]:
            stack.append((value, index))
        elif value < stack[-1][0]:
            while value < stack[-1][0]:
                if len(stack) > 1:
                    subarray_length = index-stack[-2][1]-1
                    k = min(stack[-1][0]-value, stack[-1][0]-stack[-2][0])
                    b_decreases.append([subarray_length, k])
                    stack.pop()

            if value != stack[-1][0]:
                stack.append((value, index))


    for i in range(n):
        mono_push(a[i], i)  
    mono_push(0, n)
    
    
        
    b_decreases.sort()

    for i in range(q):
        k = read()
        while len(b_decreases) > 0 and k > 0: 
            decrease_count = min(k, b_decreases[-1][1])
            total -= b_decreases[-1][0] * decrease_count
            k -= decrease_count
            b_decreases[-1][1] -= decrease_count

            if b_decreases[-1][1] == 0:
                b_decreases.pop()

        print(total)


solve()

E. The Detective Game

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

def solve():
    n = read()
    count = [0] * (n+1)
    for i in range(n):
        for j in read_list()[1:]:
            count[j] += 1

    result = []
    for i in range(1, n+1):
        if count[i] > n//2:
            result.append(i)
    print(len(result))
    print(' '.join(map(str, result)))


for i in range(read()):
    solve()

F. Distinct

CPP Solution

#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <string>
#include <iomanip>
#include <climits>
#include <functional>
#include <cctype>
#include <bitset>
#include <cassert>

using namespace std; 
 
#define all(a) a.begin(), a.end()
using ll = long long;
template<typename T> using vec = vector<T>; 
using ull = uint64_t;
#define nl '\n'
#define MOD 1000000007
#define INF (LLONG_MAX/4)
 
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;
 
template<typename type> 
struct matrix : vector<vector<type>> {
    matrix(int N, int M, type Val = {}) : 
        ::vector<vector<type>>(N, vector<type>(M, Val)){}     
}; 

template<typename T> 
using min_heap = priority_queue<T, vector<T>, greater<T>>;


struct MaxSegmentTree {
    vec<int> tree;
    int n;

    MaxSegmentTree(vec<int> const& arr) {
        n = arr.size();
        tree.assign(n*4, INT_MIN);
        build(arr, 1, 0, n-1);
    } 
    void build(vec<int> const& arr, int i, int l, int r) {
        if (l == r) {
            tree[i] = arr[l];
        } else {
            int m = (l+r)/2;
            build(arr, i*2, l, m);
            build(arr, i*2+1, m+1, r);
            tree[i] = max(tree[i*2], tree[i*2+1]);
        }
    }

    int get_max(int ql, int qr) {
        return get_max(ql, qr, 1, 0, n-1);
    } 

    int get_max(int ql, int qr, int i, int l, int r) {
        if (ql > r || qr < l) return INT_MIN;
        if (l >= ql && r <= qr) return tree[i];
        int m = (l+r) / 2;
        return max(get_max(ql, qr, i*2, l, m), get_max(ql, qr, i*2+1, m+1, r));
    }
};

struct MinSegmentTree {
    vec<int> tree;
    int n;

    MinSegmentTree(vec<int> const& arr) {
        n = arr.size();
        tree.assign(n*4, INT_MAX);
        build(arr, 1, 0, n-1);
    } 
    void build(vec<int> const& arr, int i, int l, int r) {
        if (l == r) {
            tree[i] = arr[l];
        } else {
            int m = (l+r)/2;
            build(arr, i*2, l, m);
            build(arr, i*2+1, m+1, r);
            tree[i] = min(tree[i*2], tree[i*2+1]);
        }
    }

    int first_less(int ql, int qr, int x) {
        return first_less(ql, qr, x, 1, 0, n-1);
    } 

    int first_less(int ql, int qr, int x, int i, int l, int r) {
        if (ql > r || qr < l || tree[i] >= x) return -1;
        if (l == r) return l;
        int m = (l+r) / 2;
        int left = first_less(ql, qr, x, i*2, l, m);
        if (left != -1) return left;
        return first_less(ql, qr, x, i*2+1, m+1, r);
    }
};



void solve() {
    int n, q; cin >> n >> q;
    vec<int> a(n);
    vec<int> prefix_sum(n);
    string line; cin >> line;
    for (int i=0; i<n; i++) {
        a[i] = (line[i] == '*') ? 1 : -1;        
    }

    prefix_sum[0] = a[0];
    for (int i=1; i<n; i++) {
        prefix_sum[i] = prefix_sum[i-1] + a[i];
    }
    MinSegmentTree min_seg(prefix_sum);
    MaxSegmentTree max_seg(prefix_sum);

    for (int i=0; i<q; i++) {
        int l, r; cin >> l >> r;
        l--; r--;
        ll before = (l>0) ? prefix_sum[l-1] : 0; 
        int zero_index = min_seg.first_less(l, r, before);
        ll result = 1;
        if (zero_index == -1) {
            result += max(0ll, max_seg.get_max(l, r) - before); 
        } else {
            // x becomes zero in (l, r)
            result += 1 + max(0ll, max_seg.get_max(l, zero_index) - before); 
        }
        cout << result << nl;
    }
    
}


int main(int argc, char** argv) {
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #endif
    // preprocess();
 
    int t=1;
    cin >> t;
    for (int i=0; i<t; i++){
        solve();
    }
 
}

G. String Rotation

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

def solve():
    n, x = read_list()
    s = input()
    t = input()
    result = 0
    for i in range(n):
        j = (i+n-x%n)%n
        if t[i] != s[j]:
            result += 1
    print(result)

solve()

H. Cookies

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

def solve():
    n, m, a = read_list()
    print(min(n-m, a))


for i in range(read()):
    solve()

I. Omar and Trees

CPP Solution

#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <string>
#include <iomanip>
#include <climits>
#include <functional>
#include <cctype>
#include <bitset>
#include <cassert>
 
using namespace std; 
 
#define all(a) a.begin(), a.end()
using ll = long long;
template<typename T> using vec = vector<T>; 
using ull = uint64_t;
#define nl '\n'
#define MOD 1000000007
#define INF (LLONG_MAX/4)
 
#define dbg(value) cerr << "#" #value << ": " << (value) << nl;
 
template<typename type> 
struct matrix : vector<vector<type>> {
    matrix(int N, int M, type Val = {}) : 
        ::vector<vector<type>>(N, vector<type>(M, Val)){}     
}; 
template<typename T> 
using min_heap = priority_queue<T, vector<T>, greater<T>>;



struct SegmentTree {
    // segment tree with lazy propagation

    vec<ll> tree;
    vec<ll> updated;
    int n;

    SegmentTree(int n) : n(n), tree(n*4), updated(n*4, -1) {}

    void build(vec<int> const &a) {
        build(a, 1, 0, n-1);
    } 
    void build(vec<int> const &a, int i, int l, int r) {
        if (l == r) {
            tree[i] = a[l];
        } else {
            int m = (l+r)/2;
            build(a, i*2, l, m);
            build(a, i*2+1, m+1, r);
            tree[i] = tree[i*2] + tree[i*2+1];
        }
    }

    void push(int i, int l, int r) {
        if (updated[i] != -1 && l != r){
            int m = (l+r)/2;
            tree[i*2] = (m-l+1) * updated[i];
            tree[i*2+1] = (r-m) * updated[i];
            updated[i*2] = updated[i];
            updated[i*2+1] = updated[i];
        }
        updated[i] = -1;
        
    }

    ll sum(int ql, int qr) {
        return sum(ql, qr, 1, 0, n-1);
    }

    ll sum(int ql, int qr, int i, int l, int r) {
        if (ql > r || qr < l) return 0;
        push(i, l, r);

        if (ql <= l && qr >= r) {
            return tree[i];
        } else {
            int m = (l+r)/2;
            ll result = sum(ql, qr, i*2, l, m) + sum(ql, qr, i*2+1, m+1, r);
            return result;
        }
    }


    void update_range(int ql, int qr, ll val) {
        update_range(ql, qr, val, 1, 0, n-1);
    }

    void update_range(int ql, int qr, ll val, int i, int l, int r) {
        if (ql > r || qr < l) return;
        if (ql <= l && qr >= r) {
            tree[i] = val * (r-l+1);
            updated[i] = val;
        } else {
            int m = (l+r)/2;
            push(i, l, r);
            update_range(ql, qr, val, i*2, l, m);
            update_range(ql, qr, val, i*2+1, m+1, r);
            tree[i] = tree[i*2] + tree[i*2+1];
        }
    }


};


bool check_prime(ll x) {
    for (ll d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return x >= 2;
}




vec<vec<int>> adj;
vec<int> traversal_map;
vec<int> traversal_map_out;
int dfs_index;

void dfs(int node, int prev = -1) {
    traversal_map[node] =  dfs_index++;
    for (int i: adj[node]) {
        if (i != prev) {
            dfs(i, node);
        }
    }
    traversal_map_out[node] =  dfs_index-1;
}

void solve() {
    int n; cin >> n;
    vec<int> values(n);
    adj.resize(n);
    traversal_map.resize(n);
    traversal_map_out.resize(n);

    for (int i=0; i<n; i++) {
        cin >> values[i];
    }

    for (int i=0; i<n-1; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs_index = 0;
    dfs(0);
    
    SegmentTree st(n);
    vec<int> traveral_values(n);
    for (int i=0; i<n; i++) {
        traveral_values[traversal_map[i]] = values[i];
    }
    st.build(traveral_values);

    
    int q; cin >> q;
    for (int i=0; i<q; i++) {
        int t; cin >> t;
        if (t == 2) {
            int u; cin >> u;
            u--;
            ll s = st.sum(traversal_map[u], traversal_map_out[u]);
            
            // Goldbach’s conjecture states that all even integers can be the sum of 
            // 2 primes
            // for odd numbers the sum of 2 primes should be equal to 2 + p where p is 
            // a prime 
            if (s >= 4 && (s%2 == 0 || check_prime(s - 2))) {
                cout << "YES" << nl;
            } else {
                cout << "NO" << nl;
            }

        } else {
            int u, val; cin >> u >> val;
            u--;
            st.update_range(traversal_map[u], traversal_map_out[u], val);
        }
    }
}
 


int main() {
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
    #else
        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #endif
    // preprocess();
 
    int t=1;
    // cin >> t;
    for (int i=0; i<t; i++){
        solve();
    }
 
}

J. Hide and Seek

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

def solve():
    n, x = read_list()
    h = read_list()
    result = [0] * n
    for i in range(n):
        if h[i] < x:
            result[i] = 1
    print(' '.join(map(str, result)))   


for i in range(read()):
    solve()

K. Wrong digits

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]


bits = {}

# bitmask of digit dashes
bits['0'] = 0x77;
bits['1'] = 0x12;
bits['2'] = 0x5D;
bits['3'] = 0x5B;
bits['4'] = 0x3A;
bits['5'] = 0x6B;
bits['6'] = 0x6F;
bits['7'] = 0x52;
bits['8'] = 0x7F;
bits['9'] = 0x7B;

def solve():
    n, x, y = read_list()
    s = input()
    t = input()

    dp = [[-1] * (y+1) for i in range(x+1)]
    dp[0][0] = 0;

    for i in range(n):
        for j in range(x+1):
            for k in range(y+1):
                if dp[j][k] == i:
                    for c in range(ord('0'), ord('9')+1):
                        org1 = bits[s[i]]
                        org2 = bits[t[i]]
                        dst  = bits[chr(c)]
                        j2 = j
                        k2 = k
                        j2 += ((~dst) & org1).bit_count()
                        j2 += ((~dst) & org2).bit_count()
                        k2 += ((~org1) & dst).bit_count()
                        k2 += ((~org2) & dst).bit_count()

                        if j2 <= x and k2 <= y:
                            dp[j2][k2] = max(dp[j2][k2], i+1)
                            if dp[j2][k2] == n:
                                print("YES")
                                return
    print("NO")



for i in range(read()):
    solve()

L. Black and White Tree

Python Solution


from types import GeneratorType
def stackless(f, stack=[]):
    # use this on to avoid stack overflow
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]


def solve():
    n, q = read_list()
    color = [1 if i else -1 for i in read_list()]
    g = [[] for i in range(n)] 
    result = [0] * n
    for i in range(n-1):
        a, b = read_list()
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    
    @stackless
    def dfs(node=0, prev=-1, prev_sum=0):
        freq = {} # count of all possible sums (starting from the root) of color values in this subtree 
        s = color[node] + prev_sum
        for i in g[node]: 
            if i != prev:
                next_freq = yield dfs(i, node, s)
                if len(next_freq) > len(freq):  
                    next_freq, freq = freq, next_freq
                for k, v in next_freq.items():
                    freq[k] = freq.get(k, 0) + v


        # zero sums means the number of black nodes and white node are equal
        # sums start at the root so instead of subtracting prev_sum from all values 
        # in freq we can add prev_sum to the value we're looking for which is 0
        result[node] = freq.get(prev_sum, 0) 
        freq[s] = freq.get(s, 0) + 1
        yield freq
    dfs()

    print('\n'.join(map(str, result)))



solve()

M. Delivery

Python Solution


def read():
    return int(input())

def read_list():
    return [int(i) for i in input().split()]


def solve():
    n = read()
    x = n
    while x%2 == 0:
        x //= 2

    if x == 1:
        print(-1)
        return 

    l = x//2
    r = x//2+1

    d = n // x

    r += d-1
    l -= d-1
    if l < 0:
        l = -l + 1
    
    print(l, r)


for i in range(read()):
    solve()

N. How many rectangles?

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]



class FenwickTree:
    def __init__(self, n):
        self.a = [0] * (n+1)
        self.n = n
    
    def prefix_sum(self, k):
        s = 0
        while k >= 1:
            s += self.a[k]
            k -= k&-k
        return s
    
    def add(self, k, v):
        while k <= self.n:
            self.a[k] += v
            k += k&-k


def solve():
    n = read()
    points = [] # (x, y, query index)
    compress = {}
    for i in range(n):
        _, _, x, y = read_list()
        compress[x] = 0
        compress[y] = 0
        points.append([x, y, -1])

    q = read()
    result = [0] * q
    for i in range(q):
        x, y = read_list()
        compress[x] = 0
        compress[y] = 0
        points.append([x, y, i])
    
    points.sort()
    
    compress_index = 1
    for i in sorted(compress.keys()):
        compress[i] = compress_index
        compress_index += 1

    ft = FenwickTree(len(compress))
    for x, y, q in points:
        if q == -1:
            ft.add(compress[y], 1)
        else:
            result[q] = ft.prefix_sum(compress[y])

    print('\n'.join(map(str, result)))
    
solve()

Full text and comments »

ammar007
20 months ago
2

TCPC Guide

By ammar007, history, 20 months ago, In English

TCPC Rules

Each team should have 3 contestants
Phones are not allowed
Printed material is allowed
The solution must be written in one of these programming languages: Java, C++, Python
Only one computer per team will be provided onsite for the contest (this computer has no internet connection and all the necessary tools are pre-installed)
Until the contest begins, contestants are not allowed to touch anything at the team workstation
Contest will last for 5 hours

TCPC Ranking System

The team with the most solved problems wins
In case of a tie, the team with the least wrong submission is ranked first
In case of a penalty tie, the time of the last accepted submission is considered

Previous TCPC Contests

TCPC 2023 (Problem set)
TCPC 2022 (Virtual Contest, Solutions)
TCPC 2021 (Problem set)

Some Algorithms/Data Structures Used in Past TCPC Constests

Other Useful Resources

Full text and comments »

ammar007
20 months ago
0

ACM Training Session 2024.3 -- Solutions

By ammar007, history, 2 years ago, In English

A. Collatz Algorithm

Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

n = read()
print(n, end=' ')
 
while n != 1:
    if n % 2 == 0: 
        n //= 2
    else: 
        n *= 3
        n += 1
    print(n, end=' ')

B. DNA Counting

Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]
 
 
 
s = input()
count = {}
a = "ACGT"
for c in a:
    count[c] = 0
for c in s:
    count[c] += 1

for c in a:
    print(count[c], end=' ')

C. TPCP 2023 – Is it a Helal Sequence?

Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]
 
 
n, x = read_list()
a = read_list()
 
result = 1
for i in a:
    result *= i
    result %= x
 
if result == 0:
    print("yes")
else:
    print("no")

Full text and comments »

ammar007
2 years ago
1

ACM: Intro to Graph and DFS — Solutions

By ammar007, history, 2 years ago, In English

A. Graph: Road Trip

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]

test_count = read()
for test in range(test_count):
	n, m = read_list();

	g = [[] for i in range(n+1)]
	mark = [False] * (n+1)

	for i in range(m):
		u, v = read_list()
		g[u].append(v)
		g[v].append(u)

	def dfs(node):
		if mark[node]:
			return
		mark[node] = True
		for i in g[node]:
			dfs(i)


	dfs(1)

	if mark[n]:
		print("yes")
	else:
		print("no")

C++ Solution

#include "cstdlib"
#include "cstring"
#include "cmath"
#include "iostream"
#include "stack"
#include "vector"
#include "array"
#include "queue"
#include "algorithm"
#include "map"
#include "set"
#include "unordered_map"
#include "unordered_set"
#include "numeric"
#include "string"
#include "iomanip"
#include "climits"
#include "functional"
#include "cctype"

using namespace std; 
#define array_size(a) (sizeof(a)/sizeof(a[0]))
#define rep(name, start, end) for (int name=(start); name<=(end); name++)
#define repr(name, start, end) for (int name=(start); name>=(end); name--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define MOD 1000000007
// #define MOD 998244353
#define NL '\n'
#define nl '\n'

template<typename T> 
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template<typename T> 
using max_heap = priority_queue<T>;

template<typename T> 
using matrix = vector<vector<T>>;

template<typename T> 
void _dbg(const char* name, T cont) {
	cerr << "#" << name << " = {"; 
	int n = cont.size();
	int idx = 0;
	for (auto i: cont) {
		cerr << i;
		if (++idx < n) {
			cerr << ", ";
		}
	}
	cerr << "}" << nl;
}


#ifndef ONLINE_JUDGE
#define dbg(x) _dbg(#x, x) 
#else 
#define dbg(x)
#endif

matrix<int>  g;
vector<bool> v;

void dfs(int node) {
	if (v[node]) return;
	v[node] = true;
	for (int i: g[node]) {
		dfs(i);
	}
}

void solve() {
	int n, m; cin >> n >> m;
	g.resize(n+1);
	v.resize(n+1);
	rep (i, 1, m) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1);
	if (v[n]) {
		cout << "YES" << nl;
	} else {
		cout << "NO" << nl;
	}
	g.clear();
	v.clear();
}	
	

int main() {
	#ifndef ONLINE_JUDGE 
		freopen("input.txt", "r", stdin);
		// freopen("output.txt", "w", stdout);
	#else
		ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#endif

	int t=1;
	cin >> t;
	rep(test, 1, t)  {
		solve();
	}
}

B. Graph: Counting Islands

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]
 
test_count = read()
for test in range(test_count):
	n, m = read_list();
 
	g = [[] for i in range(n+1)]
	mark = [False] * (n+1)
 
	for i in range(m):
		u, v = read_list()
		g[u].append(v)
		g[v].append(u)
 
	def dfs(node):
		if mark[node]:
			return
		mark[node] = True
		for i in g[node]:
			dfs(i)
 
	result = 0
	for i in range(1, n+1):
		if not mark[i]:
			dfs(i)
			result += 1
	print(result)

C++ Solution

#include "cstdlib"
#include "cstring"
#include "cmath"
#include "iostream"
#include "stack"
#include "vector"
#include "array"
#include "queue"
#include "algorithm"
#include "map"
#include "set"
#include "unordered_map"
#include "unordered_set"
#include "numeric"
#include "string"
#include "iomanip"
#include "climits"
#include "functional"
#include "cctype"
 
using namespace std; 
#define array_size(a) (sizeof(a)/sizeof(a[0]))
#define rep(name, start, end) for (int name=(start); name<=(end); name++)
#define repr(name, start, end) for (int name=(start); name>=(end); name--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define MOD 1000000007
// #define MOD 998244353
#define NL '\n'
#define nl '\n'
 
template<typename T> 
using min_heap = priority_queue<T, vector<T>, greater<T>>;
 
template<typename T> 
using max_heap = priority_queue<T>;
 
template<typename T> 
using matrix = vector<vector<T>>;
 
template<typename T> 
void _dbg(const char* name, T cont) {
	cerr << "#" << name << " = {"; 
	int n = cont.size();
	int idx = 0;
	for (auto i: cont) {
		cerr << i;
		if (++idx < n) {
			cerr << ", ";
		}
	}
	cerr << "}" << nl;
}
 
 
#ifndef ONLINE_JUDGE
#define dbg(x) _dbg(#x, x) 
#else 
#define dbg(x)
#endif
 
matrix<int>  g;
vector<bool> v;
 
void dfs(int node) {
	if (v[node]) return;
	v[node] = true;
	for (int i: g[node]) {
		dfs(i);
	}
}
 
void solve() {
	int n, m; cin >> n >> m;
	g.resize(n+1);
	v.resize(n+1);
	rep (i, 1, m) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int result = 0;
	rep (i, 1, n) {
		if (!v[i]) {
			dfs(i);
			result++;
		}
	}
	cout << result << nl;
	g.clear();
	v.clear();
}	
	
 
int main() {
	#ifndef ONLINE_JUDGE 
		freopen("input.txt", "r", stdin);
		// freopen("output.txt", "w", stdout);
	#else
		ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#endif
 
	int t=1;
	cin >> t;
	rep(test, 1, t)  {
		solve();
	}
}

C. Graph: Counting Rooms

Python Solution

def read():
    return int(input())
def read_list():
    return [int(i) for i in input().split()]
 
test_count = read()
for test in range(test_count):
	n, m = read_list();
 
	g = [input() for i in range(n)]
	mark = [[False] * m for i in range(n)]
 
	def dfs(i, j):
		if g[i][j] == '#' or mark[i][j]:
			return
		mark[i][j] = True
		dfs(i+1, j)
		dfs(i-1, j)
		dfs(i, j+1)
		dfs(i, j-1)
 
	result = 0
	for i in range(n):
		for j in range(m):
			if not mark[i][j] and g[i][j] == '.':
				dfs(i, j)
				result += 1
	print(result)

C++ Solution

#include "cstdlib"
#include "cstring"
#include "cmath"
#include "iostream"
#include "stack"
#include "vector"
#include "array"
#include "queue"
#include "algorithm"
#include "map"
#include "set"
#include "unordered_map"
#include "unordered_set"
#include "numeric"
#include "string"
#include "iomanip"
#include "climits"
#include "functional"
#include "cctype"
 
using namespace std; 
#define array_size(a) (sizeof(a)/sizeof(a[0]))
#define rep(name, start, end) for (int name=(start); name<=(end); name++)
#define repr(name, start, end) for (int name=(start); name>=(end); name--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define MOD 1000000007
// #define MOD 998244353
#define NL '\n'
#define nl '\n'
 
template<typename T> 
using min_heap = priority_queue<T, vector<T>, greater<T>>;
 
template<typename T> 
using max_heap = priority_queue<T>;
 
template<typename T> 
using matrix = vector<vector<T>>;
 
template<typename T> 
void _dbg(const char* name, T cont) {
	cerr << "#" << name << " = {"; 
	int n = cont.size();
	int idx = 0;
	for (auto i: cont) {
		cerr << i;
		if (++idx < n) {
			cerr << ", ";
		}
	}
	cerr << "}" << nl;
}
 
 
#ifndef ONLINE_JUDGE
#define dbg(x) _dbg(#x, x) 
#else 
#define dbg(x)
#endif
 
vector<string>  g;
vector<vector<bool>> v;
 
void dfs(int i, int j) {
	if (g[i][j] == '#' || v[i][j]) return;
	v[i][j] = true;
 
	dfs(i,j+1);
	dfs(i,j-1);
	dfs(i+1,j);
	dfs(i-1,j);
}
 
void solve() {
	int n, m; cin >> n >> m;
	g.resize(n);
	v.resize(n, vector<bool>(m));
	rep (i, 0, n-1) {
		cin >> g[i];
	}
	int result = 0;
	rep (i, 0, n-1) {
		rep (j, 0, m-1) {
			if (!v[i][j] && g[i][j] == '.') {
				dfs(i, j);
				result++;
			}
		}
	}
	cout << result << nl;
	g.clear();
	v.clear();
}	
	
 
int main() {
	#ifndef ONLINE_JUDGE 
		freopen("input.txt", "r", stdin);
		// freopen("output.txt", "w", stdout);
	#else
		ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	#endif
 
	int t=1;
	cin >> t;
	rep(test, 1, t)  {
		solve();
	}
}

Full text and comments »

ammar007
2 years ago
1

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	turmax	3559
6	tourist	3541
7	strapple	3515
8	ksun48	3461
9	dXqwq	3436
10	Otomachi_Una	3413

#	User	Contrib.
1	Qingyu	157
2	adamant	153
3	Um_nik	147
4	Proof_by_QED	146
5	Dominater069	145
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133