結果
| 問題 |
No.3104 Simple Graph Problem
|
| ユーザー |
 Astral__
|
| 提出日時 | 2025-04-11 23:16:14 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 334 ms / 2,000 ms |
| コード長 | 15,458 bytes |
| コンパイル時間 | 6,782 ms |
| コンパイル使用メモリ | 333,308 KB |
| 実行使用メモリ | 60,596 KB |
| 最終ジャッジ日時 | 2025-04-11 23:16:32 |
| 合計ジャッジ時間 | 17,438 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 65 |
ソースコード
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
std::istream &operator>>(std::istream &is, atcoder::modint &v) {
long long value;
is >> value;
v = value;
return is;
}
std::ostream &operator<<(std::ostream &os, const atcoder::modint &v) {
os << v.val();
return os;
}
std::ostream &operator<<(std::ostream &os, const atcoder::modint998244353 &v) {
os << v.val();
return os;
}
std::istream &operator>>(std::istream &is, atcoder::modint998244353 &v) {
long long x;
is >> x;
v = x;
return is;
}
std::ostream &operator<<(std::ostream &os, const atcoder::modint1000000007 &v) {
os << v.val();
return os;
}
std::istream &operator>>(std::istream &is, atcoder::modint1000000007 &v) {
long long x;
is >> x;
v = x;
return is;
}
#endif
using namespace std;
using ll = long long;
using lint = __int128_t;
using pll = pair<ll, ll>;
#define newl '\n';
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define SZ(x) ll(x.size())
#define eb emplace_back
#define pb push_back
#define TT template <typename T>
TT using vec = vector<T>;
TT using vvec = vec<vec<T>>;
TT using vvvec = vec<vvec<T>>;
TT using minheap = priority_queue<T, vector<T>, greater<T>>;
TT using maxheap = priority_queue<T>;
TT bool chmin(T &x, T y) {
return x > y ? (x = y, true) : false;
}
TT bool chmax(T &x, T y) {
return x < y ? (x = y, true) : false;
}
TT T smod(T x, T mod) {
x %= mod;
if (x < 0)
x += mod;
return x;
}
TT bool rng(T l, T x, T r) {
return l <= x && x < r;
}
TT T flr(T a, T b) {
if (b < 0)
a = -a, b = -b;
return a >= 0 ? a / b : (a + 1) / b - 1;
}
TT T cil(T a, T b) {
if (b < 0)
a = -a, b = -b;
return a > 0 ? (a - 1) / b + 1 : a / b;
}
TT T sqr(T x) {
return x * x;
}
//{0, 1, ... } -> {p[0], p[1], ...}
template <typename T, typename S>
void rearrange(vector<T> &A, vector<S> const &p) {
assert(p.size() == A.size());
vector<T> a = A;
for (int i = 0; i < ssize(A); ++i) {
a[i] = A[p[i]];
}
swap(a, A);
}
template <typename T, typename S, typename... Ts>
void rearrange(vector<T> &A, vector<S> p, vector<Ts> &...rest) {
rearrange(A, p);
(rearrange(rest, p), ...);
}
template <typename T, typename Compare, typename... Ts>
void rearrange(vector<T> &A, Compare cmp, vector<Ts> &...rest) {
vector<int> p(ssize(A));
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), cmp);
rearrange(A, p);
(rearrange(rest, p), ...);
}
struct io_setup {
io_setup() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} io_setup;
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
TT ostream &operator<<(ostream &os, const vector<T> &v) {
for (size_t i = 0; i < v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, const array<T, n> &v) {
for (size_t i = 0; i < n; i++) {
os << v[i] << (i + 1 != n ? " " : "");
}
return os;
}
template <typename T> ostream &operator<<(ostream &os, const vvec<T> &v) {
for (size_t i = 0; i < v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? "\n" : "");
}
return os;
}
TT istream &operator>>(istream &is, vector<T> &v) {
for (size_t i = 0; i < v.size(); i++) {
is >> v[i];
}
return is;
}
#if __has_include(<debug/debug.hpp>)
#include <debug/debug.hpp>
#else
#define dbg(...) true
#define DBG(...) true
#define OUT(...) true
#endif
template <typename T> struct Edge {
int to;
T cost;
int id;
static constexpr T INF = numeric_limits<T>::max() / 2;
Edge(int to = 0, T cost = 1, int id = -1) : to(to), cost(cost), id(id) {
}
};
template <typename T, bool directed> struct Graph : vector<vector<Edge<T>>> {
#define n int(this->size())
using vector<vector<Edge<T>>>::vector;
void add(int s, int t, T w = 1, int id = -1) {
(*this)[s].emplace_back(t, w, id);
if constexpr (directed == false) {
(*this)[t].emplace_back(s, w, id);
}
}
#undef n
};
template <typename T> struct Tree : Graph<T, false> {
#define n int(this->size())
using Graph<T, false>::Graph;
#undef n
};
namespace Graph_lib {
#define inf Edge<T>::INF
template <typename T, bool directed>
vector<T> DFS(Graph<T, directed> const &g, int s) {
int n = g.size();
assert(0 <= s && s < n);
vector<T> d(n, inf);
d[s] = 0;
queue<int> que;
que.push(s);
while (que.empty() == false) {
int v = que.front();
que.pop();
for (auto &e : g[v]) {
assert(e.cost == 1);
if (chmin(d[e.to], d[v] + e.cost)) {
que.push(e.to);
}
}
}
return d;
}
template <typename T, bool directed>
vector<T> dijkstra(Graph<T, directed> const &g, int s) {
int n = g.size();
vector<T> d(n, inf);
d[s] = 0;
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>>
que;
que.push({d[s], s});
while (que.empty() == false) {
auto [c, v] = que.top();
que.pop();
if (d[v] < c)
continue;
for (auto &e : g[v]) {
assert(e.cost >= 0);
if (chmin(d[e.to], d[v] + e.cost)) {
que.push({d[e.to], e.to});
}
}
}
return d;
}
template <typename T, bool directed>
pair<bool, vector<T>> bellman_ford(Graph<T, directed> const &g, int s) {
int n = g.size();
vector<T> d(n, inf);
d[s] = 0;
int last = -1;
for (int i = 0; i <= n; i++) {
bool f = false;
for (int v = 0; v < n; v++)
if (d[v] != inf) {
for (auto &e : g[v]) {
if (chmin(d[e.to], d[v] + e.cost)) {
f = true;
}
}
}
if (f)
last = i;
}
if (last == n)
return {true, d};
else
return {false, d};
}
template <typename T, bool directed>
bool has_negative_cycle(Graph<T, directed> const &g) {
if (g.size() == 0)
return false;
auto [f, d] = bellman_ford(g, 0);
return f;
}
template <typename T, bool directed>
vector<vector<T>> warshall(Graph<T, directed> const &g) {
int n = g.size();
vector<vector<T>> d(n, vector<T>(n, inf));
for (int i = 0; i < n; i++) {
d[i][i] = 0;
for (auto &e : g[i]) {
chmin(d[i][e.to], e.cost);
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
if (d[i][k] == inf)
continue;
for (int j = 0; j < n; j++) {
if (d[k][j] == inf)
continue;
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
return d;
}
template <typename T, bool directed>
pair<vector<int>, vector<int>> cycle_detection(Graph<T, directed> const &g,
int v = -1) {
int n = g.size();
vector<bool> in(n, false), out(n, false);
vector<int> vs, es;
const int fin = INT_MAX;
auto dfs = [&](auto f, int v, int p) -> int {
bool prev_edge = false;
in[v] = true;
for (auto e : g[v]) {
if constexpr (directed == false) {
if (e.to == p) {
if (prev_edge == false) {
prev_edge = true;
continue;
} else {
vs.push_back(v);
es.push_back(e.id);
out[v] = true;
return e.to;
}
}
}
if (in[e.to] && out[e.to] == false) {
vs.push_back(v);
es.push_back(e.id);
out[v] = true;
return v == e.to ? fin : e.to;
}
if (in[e.to] == false) {
int root = f(f, e.to, v);
if (root != -1 && root != fin) {
vs.push_back(v);
es.push_back(e.id);
out[v] = true;
return (v == root ? fin : root);
} else if (root == fin) {
out[v] = true;
return fin;
}
}
}
out[v] = true;
return -1;
};
int s = 0, t = n;
if (v != -1)
s = v, t = v + 1;
for (int i = s; i < t; i++) {
if (in[i] == false) {
dfs(dfs, i, -1);
if (vs.empty() == false) {
reverse(vs.begin(), vs.end());
reverse(es.begin(), es.end());
return make_pair(vs, es);
}
}
}
return make_pair(vs, es);
}
// ret[v] := vを含む連結成分が
// -1 : 二部グラフでない 0 : 色塗ったら0 1 : 色塗ったら1
// 色塗りは0から始める
template <typename T, bool directed>
vector<int> bipartite_check(Graph<T, directed> const &g) {
int n = g.size();
vector<int> col(n, -1);
vector<vector<int>> gs;
auto dfs = [&](auto f, int v, int c, vector<int> &vs) -> void {
col[v] = c;
vs.push_back(v);
for (auto &e : g[v])
if (col[e.to] == -1) {
f(f, e.to, c ^ 1, vs);
}
};
for (int i = 0; i < n; i++) {
if (col[i] == -1) {
vector<int> vs;
dfs(dfs, i, 0, vs);
gs.push_back(vs);
}
}
for (auto &vs : gs) {
bool ng = false;
for (auto v : vs) {
for (auto &e : g[v]) {
if (col[v] == col[e.to]) {
ng = true;
}
}
}
if (ng) {
for (auto v : vs)
col[v] = -1;
}
}
return col;
}
#undef inf
}; // namespace Graph_lib
namespace Tree_lib {
#define inf Edge<T>::INF
template <typename T> vector<T> dist(Tree<T> const &tr, int s) {
int n = tr.size();
vector<T> res(n, inf);
res[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto &e : tr[v])
if (chmin(res[e.to], res[v] + e.cost)) {
que.push(e.to);
}
}
return res;
}
template <typename T> vector<int> path(Tree<T> const &tr, int s, int t) {
vector<int> res;
auto dfs = [&](auto f, int v, int p = -1) -> bool {
if (v == t) {
return true;
}
for (auto &e : tr[v])
if (e.to != p) {
if (f(f, e.to, v)) {
res.push_back(e.to);
return true;
}
}
return false;
};
dfs(dfs, s);
res.push_back(s);
reverse(res.begin(), res.end());
return res;
}
// diam() ... (直径, (直径の端u, 直径の端v))
template <typename T> pair<T, pair<int, int>> diam(Tree<T> const &tr) {
int n = tr.size();
int u, v;
T d, tmp;
vector<T> ds = dist(tr, 0);
tmp = ds[0], u = 0;
for (int i = 1; i < n; i++) {
if (chmax(tmp, ds[i]))
u = i;
}
vector<T> ds2 = dist(tr, u);
d = ds2[0], v = 0;
for (int i = 1; i < n; i++) {
if (chmax(d, ds2[i]))
v = i;
}
pair<T, pair<int, int>> res;
res.first = d;
res.second.first = u;
res.second.second = v;
return res;
}
// {直径0, 直径1 or -1}
template <typename T> pair<int, int> center(Tree<T> const &tr) {
auto [d, p] = diam(tr);
auto ph = path(tr, p.first, p.second);
int m = (ph.size() + 1) / 2 - 1;
if (ph.size() % 2 == 1)
return {ph[m], -1};
else
return {ph[m], ph[m + 1]};
}
template <typename T>
vector<pair<int, int>> maximum_matching(Tree<T> const &tr) {
vector<pair<int, int>> ret;
auto dfs = [&](auto f, int v, int p) -> bool {
bool used = false;
for (auto &e : tr[v])
if (e.to != p) {
bool used_to = f(f, e.to, v);
if (used_to == false && used == false) {
used = true;
ret.emplace_back(v, e.to);
}
}
return used;
};
dfs(dfs, 0, -1);
return ret;
}
//{存在するか、頂点のペアの集合}
template <typename T>
pair<bool, vector<pair<int, int>>> perfect_matching(Tree<T> const &tr) {
if (tr.size() % 2 == 1)
return {false, {}};
auto match = maximum_matching(tr);
if (match.size() * 2 == tr.size()) {
return {true, match};
} else {
return {false, match};
}
}
#undef inf
}; // namespace Tree_lib
using mint = atcoder::modint998244353;
using P = array<ll, 3>;
/*
x=0にすると、操作を無視できる
いつもの全域木
*/
pair<bool, vector<mint>> solve(ll n, ll m, vector<ll> B, Graph<ll, false> g,
map<pll, ll> id) {
{
auto col = Graph_lib::bipartite_check(g);
if (col[0] != -1) {
vector<mint> sm(2, 0);
rep(i, 0, n) sm[col[i]] += B[i];
if (sm[0] != sm[1]) {
return {false, {}};
}
}
}
atcoder::dsu uf(n);
Tree<ll> tr(n);
rep(i, 0, n) for (auto e : g[i]) {
if (uf.same(i, e.to) == false) {
uf.merge(i, e.to);
tr.add(i, e.to);
}
}
auto col = Graph_lib::bipartite_check(tr);
vector<mint> sm(2, 0);
rep(i, 0, n) sm[col[i]] += B[i];
vector<pll> same(2, pll(-1, -1));
rep(i, 0, n) for (auto e : g[i]) if (col[i] == col[e.to]) {
same[col[i]] = pll(i, e.to);
}
vector<mint> A(n, 0);
map<pll, mint> ret;
auto add = [&](ll u, ll v, mint val) {
ret[minmax(u, v)] += val;
A[u] += val;
A[v] += val;
};
if (same[0] != pll(-1, -1)) {
mint v = (sm[1] - sm[0]) / 2;
add(same[0].first, same[0].second, -v);
// sm[0] += 2*v;
} else if(same[1] != pll(-1, -1)) {
mint v = (sm[0] - sm[1]) / 2;
add(same[1].first, same[1].second, -v);
// sm[1] += 2*v;
}
auto dfs = [&](auto f, int v, int p) -> void {
for (auto e : tr[v])
if (e.to != p) {
f(f, e.to, v);
mint d = B[e.to] - A[e.to];
add(v, e.to, d);
};
return;
};
dfs(dfs, 0, -1);
vector<mint> ans(m, 0);
for (auto p : ret) {
auto [uv, val] = p;
ans[id[uv]] += val;
}
return {true, ans};
}
int main() {
ll n, m;
cin >> n >> m;
vector<ll> B(n);
cin >> B;
Graph<ll, false> g(n);
map<pll, ll> id;
rep(i, 0, m) {
ll u, v;
cin >> u >> v;
u--, v--;
g.add(u, v);
id[minmax(u, v)] = i;
}
auto [flg, ret] = solve(n, m, B, g, id);
if(flg == false) {
cout << -1 << endl;
}
else {
cout << ret << endl;
}
}
/*
同じ議論を繰り返さない
do smth instead of nothing and stay organized
WRITE STUFF DOWN
DON'T GET STUCK ON ONE APPROACH
*/