| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 440447 | antontsiorvas | Fountain Parks (IOI21_parks) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int fount2[200005], fount4[200005];
int sy2[200005], sy4[200005];
int numofvis;
vector<int> data[200005];
map<int,int> emf;
bool visited[200005];
bool compare2(int a, int b){ return sy2[a] < sy2[b]; }
bool compare4(int a, int b){ return sy4[a] < sy4[b]; }
void dfs(int v){
visited[v] = true;
numofvis++;
int len = data[v].size();
for(int i=0; i<len; i++){
int to = data[v][i];
if(!visited[to]) dfs(to);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size(), cnt2=0, cnt4=0;
for(int i=0; i<n; i++){
if(x[i] == 2){
fount2[cnt2] = i;
sy2[cnt2++] = y[i];
}
else{
fount4[cnt4] = i;
sy4[cnt4++] = y[i];
}
}
std::sort(&fount2[0],&fount2[cnt2],compare2);
std::sort(&sy2[0],&sy2[cnt2]);
std::sort(&fount4[0],&fount4[cnt4],compare4);
for(int i=1; i<cnt4; i++) emf[sy4[i]] = i;
emf[sy4[0]] = -1;
std::sort(&sy4[0],&sy4[cnt4]);
std::vector<int> u, v, a, b;
if(cnt2 == 0){
for(int i=0; i<cnt4-1; i++){
if(sy4[i+1]-sy4[i] != 2) return 0;
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
}
build(u, v, a, b);
return 1;
}
if(cnt4 == 0){
for(int i=0; i<cnt2-1; i++){
if(sy2[i+1]-sy2[i] != 2) return 0;
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
}
build(u, v, a, b);
return 1;
}
for(int i=0; i<cnt2; i++){
if(i == cnt2-1) continue;
while(sy2[i+1]-sy2[i] == 2){
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
i++;
}
}
for(int i=0; i<cnt4; i++){
if(i == cnt4-1) continue;
while(sy4[i+1]-sy4[i] == 2){
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
i++;
}
}
for(int i=0; i<cnt2; i++){
int temp = emf[sy2[i]];
if(temp == 0) continue;
if(temp == -1) temp = 0;
u.push_back(i);
v.push_back(fount4[temp]);
a.push_back(3);
b.push_back(sy2[i]-1);
}
int s = u.size();
for(int i=0; i<s; i++){
data[u[i]].push_back(v[i]);
data[v[i]].push_back(u[i]);
}
dfs(u[0]);
if(numofvis != n) return 0;
build(u, v, a, b);
return 1;
}