www.acmicpc.net/problem/10169 10169번: 안전한 비상연락망 입력의 첫 줄에는 마을의 수 N (2 ≤ N ≤ 100,000)과 도로의 수 M (2 ≤ M ≤ 300,000)이 자연수로 주어진다. 각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주 www.acmicpc.net 도로 하나가 없어졌을때마다 mst를 구하는 문제다. 일단 두가지 경우로 나눌 수 있는데, i) 기본 mst에 포함되지 않는 도로인 경우 ii) 기본 mst에 포함된 도로인 경우 i)에 대해서는 답이 변하지 않는다는 것을 알 수 있다. 이제 ii)에 대한 처리가 문제인데, 일단 mst로 만들어진 도로로 트리를 만든다. 검은색 : mst에 포함된 도로, 빨간색 : 포함..
www.acmicpc.net/problem/18913 18913번: Graph Coloring You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors. There www.acmicpc.net 내가 푼 문제중에 재밌던 문제의 풀이를 블로그에 올린다. 그래프의 간선들에 \(a\)~\(n\)의 색을 매길건데, 어떤 경로 \(x..
오랜만에 딥3가 나와서 한번 쳐봤다. 올솔이 1시간 컷이 나는거 보니 실력이 늘긴 늘었나 보다 (옛날엔 딥3 4~5솔..) D 까지는 간단하게 설명해 주겠다. (사실 거의 다 간단간단해서 편하게 듣는게 좋을 것 같다) A - Boring Apartments (1분) 그냥 시뮬레이션 문제다. #include #define x first #define y second #define pb push_back #define all(v) v.begin(),v.end() #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; const int INF = 1e9; con..
- Total
- Today
- Yesterday
- 앳코더
- combination
- 세그먼트 트리
- 누적 합
- codeforces
- 비요뜨 존맛
- 스택
- DP
- 하이퍼
- 수열과 쿼리
- 오일러 경로
- 냄새 싫어
- PS
- 쿼리
- hyper
- AtCoder
- 김춘배
- 1909
- 정렬
- gunwookim
- Offline Dynamic Connectivity
- 비요뜨
- 알고리즘 문제 풀이
- BOJ
- ABC
- 간단한 풀이
- Rabin-Karp
- Constructive
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |