주어진 그래프가 사이클이 없으므로, 나머지를 어떻게 연결하던 사이클이 없는 그래프는 반드시 생성 가능함 나머지 간선을 한 방향으로 연결해보고, 사이클이 생기면 반대방향이 정답 사이클 판단에 N+K+M, M번 반복하므로 시간안에 해결 /* Prob 2021 SCPC 1차 예선 3번 No Cycle */ #include #include #define N 510 using namespace std; int tc, n, k, m; vector edges[N]; bool checked[N], finished[N]; bool hasCycle(int now) { if (checked[now]) return !finished[now]; checked[now] = true; for (int next : edges[now..
/* Prob 2021 SCPC 예선 2번 이진수 */ #include #include #define N 50010 using namespace std; int tc, n, t; string line; bool b[N]; void solve() { bool a[N] = {0}; for (int i = 1; i > t >> line; for (int i = 1; i
/* Prob 2021 SCPC 예선 1번 친구들 */ #include #include #define N 100010 using namespace std; int tc, n; int arr[N], ds[N]; void uni(int a, int b) { if (a > b) swap(a, b); ds[a] = b; } int find(int a) { if (ds[a] == a) return a; return ds[a] = find(ds[a]); } int solve() { int ans = 0; for (int i = 1; i tc; for (int tt = 1; tt > n; for (int i = 1; i > arr[i]; cout
struct Node { vector childs; Node() {}; }; Node nodes[100001]; int depth[100001]; int lca[100001][20]; void updateLca(int idx, int parent, int k) { if(parent == 0) return; lca[idx][k] = parent; updateLca(idx, lca[parent][k], k + 1); } int findLca(int a, int b, int k) { if(a == b) return a; if(lca[a][0] == lca[b][0]) return lca[b][0]; if(lca[a][k + 1] != lca[b][k + 1]) return findLca(a, b, k + 1)..
문제 해결 수열에서 인접한 원소들의 차들의 최대공약수의 약수의 개수가 가능한 공차의 개수 $O(N \cdot \log N)$ 최소공약수 $O( \log N)$ 소스코드 /* Prob SCPC 1회 예선 등차수열 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int tc, n; long getGcd(long a, long b) { if(a > n; for(int i = 0; i < n; i++)..
문제 해결 최대 전원거리는 $최대 Chebyshev / 2$ LineA -> LineB의 최대 Chebyshev 거리를 구하되, 기준이 되는 점을 따로 잡아야 함 LineA의 pt1 -> 나머지Line들의 Chebyshev 거리의 최댓값 = ChebyshevA LineA의 pt2 -> 나머지Line들의 Chebyshev 거리의 최댓값 = ChebyshevB LineA -> 나머지Line 에 대한 전원거리는 $min(ChebyshevA / 2, ChebyshevB / 2)$ $O(N^2)$ 소스코드 /* Prob SCPC 1회 예선 회로판 위의 배터리 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; in..
문제 해결 모든 n은 n-1진수일 때 11로 표현할 수 있음 n을 b진수로 표현할 때 b가 커질 수록 자릿수가 줄어듬 $n = b \cdot d + d = d(b + 1)$ $b > d$이므로, d가 최대일 때 $d = b - 1$ $n = b ^ 2 - 1 $ $b = \sqrt{n + 1}$ 즉 q가 최대여도 $\sqrt{n + 1}$진수 까지만 확인하면 되므로 $\sqrt{1000000001} \approx 31623$ 까지만 확인하여 시간초과 방지 예외적으로 두자릿수로 표현되는 b진수는 위 식이 성립되지 않으므로 $n = d(b + 1)$ 식에서 d를 하나씩 대입해보며 최소의 b를 찾는다 소스코드 /* Prob SCPC 1회 예선 균일수 Writer MyungSeung Kim(mskim9967@g..
문제 해결 구현, 방향마다 반사되는 방법이 정해져 있으므로 그대로 구현하면 됨 소스코드 /* Prob SCPC 1회 예선 방속의 거울 Writer MyungSeung Kim(mskim9967@gmail.com) */ #include #include using namespace std; int tc, n, k; int mmap[1010][1010]; bool check[1010][1010]; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; void solve() { int ans = 0, x = 0, y = 0, dir = 0; memset(check, false, sizeof(check)); cin >> n; for(int i = 0; i < n; i++) { s..
Comment