목록Problem Solving (223)
Life Engineering
https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net #include #define ll long long using namespace std; int parents[100001]; ll diff[100001]; //root 와의 차이 int find(int a){ if (parents[a]==a){ return a; } int p=find(parents[a]); diff[a]+=diff[parents[a]]; //갱신 ..
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net #include #define MAX 1000000001 using namespace std; long* tree_min; long* tree_max; void init(int S){ for (int i=S-1; i>0; i--){ tree_min[i]=min(tree_min[i*2], tree_min[i*2+1]); tree_max[i]=max(tree_ma..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net #include using namespace std; int student[100001]; bool visited[100001]; bool group[100001]; int cnt; void dfs(int x){ visited[x]=true; int next=student[x]; if (!visited[next]){ dfs(next); } else if (!group[next]){ //방문 전에 했지만..
https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net #include using namespace std; int parent[100000]; class Edge{ public: int a; int b; long cost; Edge(int a, int b, long cost){ this->a=a; this->b=b; this->cost=cost; } }; bool sortX(const pair&v1, const pai..