# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
443296 | mkisic | Split the Attractions (IOI19_split) | C++14 | 97 ms | 13152 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <queue>
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define pb push_back
const int MAXN = 200100;
int n;
vector <int> v[MAXN];
vector <int> bio;
bool bfs(int start, vector <int> boje, vector <int> &ret) {
queue <int> q;
bio[start] = 1;
int cnt = 0;
q.push(start);
vector <int> pos;
while (!q.empty()) {
int cvor = q.front();
q.pop();
cnt++;
pos.pb(cvor);
if (cnt == min(boje[2], boje[3])) {
int boja = 3;
if (boje[3] > boje[2]) boja = 2;
for (auto &x : pos) ret[x] = boja;
return true;
}
for (auto &ncvor : v[cvor]) {
if (bio[ncvor]) continue;
bio[ncvor] = 1;
q.push(ncvor);
}
}
return false;
}
vector <int> solve1(vector <int> boje) {
vector <int> ret;
ret.resize(n);
REP(i, n) {
if (bio[i]) continue;
if (bfs(i, boje, ret)) {
int boja = 2;
if (boje[3] > boje[2]) boja = 3;
REP(j, n) {
if (ret[j] == 0 && boje[1]) {
ret[j] = 1;
boje[1]--;
} else if (ret[j] == 0) ret[j] = boja;
}
return ret;
}
}
return ret;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
bio.resize(n);
REP(i, p.size()) {
v[p[i]].pb(q[i]);
v[q[i]].pb(p[i]);
}
vector <int> boje = {0, a, b, c};
return solve1(boje);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |