# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
43843 | Bruteforceman | Pipes (BOI13_pipes) | C++11 | 347 ms | 20744 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
bool vis[100010];
int l[500010], r[500010];
vector <int> g[100010];
long long a[100010];
bool del[500010];
int deg[100010];
long long ans[500010];
vector <int> can;
bool bad;
void check(int x) {
vis[x] = true;
can.push_back(x);
int deg = 0;
for(auto i : g[x]) {
if(del[i]) continue;
int y = l[i] ^ r[i] ^ x;
++deg;
if(vis[y] == false) check(y);
}
if(deg != 2 && deg != 0) {
bad = true;
}
}
int edge(int x, int y) {
for(auto i : g[x]) {
int p = l[i] ^ r[i] ^ x;
if(p == y) return i;
}
return -1;
}
void solve(vector <int> v) {
int size = v.size();
vector <long long> Odd (size), Even (size);
long long odd = 0;
long long even = 0;
long long sum = 0;
for(int i = 0; i < size; i++) {
if(i & 1) {
odd += a[v[i]];
} else {
even += a[v[i]];
}
Even[i] = even;
Odd[i] = odd;
sum += a[v[i]];
}
if(sum % 2 != 0) {
printf("0\n");
exit(0);
}
sum /= 2;
for(int i = 0; i < size; i++) {
int p = v[i];
int q = v[(i + 1) % size];
int id = edge(p, q);
if(i & 1) {
ans[id] = Even[i];
ans[id] += odd - Odd[i];
} else {
ans[id] = Odd[i];
ans[id] += even - Even[i];
}
ans[id] = sum - ans[id];
}
}
int main(int argc, char const *argv[])
{
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
queue <int> Q;
for(int i = 1; i <= m; i++) {
int p, q;
scanf("%d %d", &p, &q);
g[p].push_back(i);
g[q].push_back(i);
l[i] = p;
r[i] = q;
}
for(int i = 1; i <= n; i++) {
deg[i] = g[i].size();
if(g[i].size() == 1) {
Q.push(i);
}
}
while(!Q.empty()) {
int p = Q.front();
Q.pop();
if(deg[p] != 1) {
if(a[p] != 0) {
printf("0\n");
exit(0);
}
continue;
}
for(auto i : g[p]) {
if(del[i] == true) continue;
int j = l[i] ^ r[i] ^ p;
deg[j]--;
if(deg[j] == 1) {
Q.push(j);
}
ans[i] = a[p];
a[j] -= a[p];
del[i] = true;
}
}
for(int i = 1; i <= n; i++) {
if(vis[i] == false) {
bad = false;
can.clear();
check(i);
if(can.size() % 2 == 0) {
bad = true;
}
if(bad) {
printf("0\n");
exit(0);
}
if(can.size() > 1) {
solve(can);
}
}
}
for(int i = 1; i <= m; i++) {
printf("%lld\n", ans[i] << 1);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |