| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 107259 | batmend_kh | 친구 (IOI14_friend) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
struct edge{
int bg;
int en;
int flow;
edge (int bg, int en, int flow) {
this -> bg = bg;
this -> en = en;
this -> flow = flow;
}
};
int height, width, n_banks;
vector<edge> edges;
vector<vector<pair<int, int> > > adj;
pair<int, int> parent[6005];
int get_in(int h, int w) {
return h * width + w;
}
int get_out(int h, int w) {
return get_in(h, w) + 3000;
}
void make_edge(int bg, int en) {
edges.push_back(edge(bg, en, 1));
adj[bg].push_back(make_pair(en, edges.size() - 1));
adj[en].push_back(make_pair(bg, edges.size() - 1));
}
bool found_path() {
queue <int> q;
for (int i = 0; i <= 6001; i++) parent[i] = make_pair(-1, -1);
q.push(6000);
parent[6000] = make_pair(0, 0);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i < adj[current].size(); i++) {
if (parent[adj[current][i].first] != make_pair(-1, -1)) continue;
edge x = edges[adj[current][i].second];
int bg = x.bg;
int en = x.en;
if (current == bg && x.flow == 1) {
parent[en] = make_pair(bg, i);
q.push(en);
}
if (current == en && x.flow == 0) {
parent[bg] = make_pair(en, i);
q.push(bg);
}
}
}
if (parent[6001] == make_pair(-1, -1)) return 0;
else return 1;
}
int main() {
int q_;
cin >> q_;
while (q_--) {
cin >> width >> height >> n_banks;
int answer = 0;
edges.clear();
adj = vector<vector<pair<int, int> > > (6005);
for (int i = 1; i <= height; i++) {
for (int j = 1; j <= width; j++) {
make_edge(get_in(i, j), get_out(i, j));
if (i - 1 > 0) make_edge (get_out(i, j), get_in(i - 1, j));
if (j - 1 > 0) make_edge (get_out(i, j), get_in(i, j - 1));
if (i + 1 <= height) make_edge (get_out(i, j), get_in(i + 1, j));
if (j + 1 <= width) make_edge (get_out(i, j), get_in(i, j + 1));
if (i - 1 == 0 || j - 1 == 0 || i + 1 > height || j + 1 > width) make_edge (get_out(i, j), 6001);
}
}
for (int i = 0, x, y; i < n_banks; i++) {
cin >> x >> y;
make_edge(6000, get_in(y, x));
}
while (found_path()) {
answer++;
for (int i = 6001; i != 6000; i = parent[i].first) {
edges[adj[parent[i].first][parent[i].second].second].flow ^= 1;
}
}
if (answer == n_banks) cout << "possible" << '\n';
else cout << "not possible" << '\n';
}
}