ACL Beginner Contest
はい。
ACL Beginner Contest
ooox-- 817(-9) 茶色がかなり現実的に。
A - Repeat ACL
PyPy3
n=int(input()) print("ACL"*n)
*n
するとn回出力は便利。
B - Integer Preference
PyPy3
a,b,c,d=map(int,input().split()) print("Yes" if (a<=c<=b or a<=d<=b or c<=a<=d or c<=b<=d) else "No")
雑な書き方、雑な確認で無駄にWAしました。 公式解説の (max(A, C) <= min(B, D)
はコンテスト中に自力で気づかなくても気にしなくていいと思います。。
C - Connect Cities
#include<bits/stdc++.h> using namespace std; struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) {} bool unite(int x, int y) { x=root(x), y=root(y); if (x!=y) { if (data[y]<data[x]) { swap(x, y); } data[x]+=data[y], data[y]=x; } return x!=y; } bool find(int x, int y) { return root(x)==root(y); } int root(int x) { return data[x]<0 ? x : data[x]=root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main(){ int n,q,ans=0; scanf("%d %d",&n,&q); UnionFind uf(n); for (int i=0;i<q;i++) { int a,b; scanf("%d %d",&a,&b); uf.unite(a-1,b-1); } set<int> s; for (int i=0;i<n;i++) { s.insert(uf.root(i)); //printf("%d\n",uf.root(i)); } printf("%ld\n",s.size()-1); return 0; }
UnionFindを使う。入力の辺を処理した後に分かれているグループの数-1の道路を造れば全て繋がります。
D問題以降はあとで