>
using namespace std;
#define ff endl
#define lf "\n"
#define fi first
#define se second
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define infor(str, ...) do { fprintf(stderr, str, ##__VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", ##__VA_ARGS__); } while(0)
#ifndef DEBUG
#undef infor
#undef infof
#define infor(str, ...)
#define infof(str, ...)
#endif
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 6e5+7;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int N, K; cin >> N >> K;
vector<pii> ed(2 * N);
vector<int> W(2 * N), dg(2 * N);
vector<vector<pii>> adj(2 * N);
for(int i = 0; i < 2 * N; ++i) {
auto &[u, v] = ed[i];
cin >> u >> v >> W[i];
u -= 1, v += N - 1;
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
dg[u] += 1;
dg[v] += 1;
}
queue<int> q;
for(int i = 0; i < 2 * N; ++i) {
if(dg[i] == 1) q.emplace(i);
}
infof("===== toposort =====");
while(!q.empty()) {
auto v = q.front(); q.pop();
for(auto [u, w]: adj[v]) {
dg[u] -= 1;
if(dg[u] != 1) continue;
q.emplace(u);
}
}
infor("dg:");
for(auto x: dg) {
infor(" %d", x);
}
infof("");
vector<bool> vis(2 * N);
auto dfs = [&](int v, int f, auto &&dfs) -> int {
if(vis[v]) return 0;
vis[v] = 1;
infof("===== dfs(%d, %d) =====", v + 1, f);
infof("... dg[v] = %d", dg[v]);
for(auto [u, w]: adj[v]) {
if(w == f || dg[u] < 2) continue;
infof("... %d: u = %d", v + 1, u + 1);
int x = dfs(u, w, dfs);
infof("... %d: ret W[w] - x = %d - %d = %d",
v + 1, W[w], x, W[w] - x);
return W[w] - x;
}
assert(0);
};
vector<int> V;
for(int i = 0; i < 2 * N; ++i) {
if(dg[i] < 2) continue;
int x = dfs(i, -1, dfs);
infof("dfs(%d) -> %d", i + 1, x);
if(x) V.emplace_back(abs(x));
}
vector<array<bool, 2>> ok(2 * N);
queue<pii> q2;
for(int i = 0; i < 2 * N; ++i) {
if(!vis[i]) continue;
int k = i >= N;
for(auto [u, w]: adj[i]) {
if(dg[u] == 2) continue;
ok[w][k] = 1;
if(vis[u]) continue;
vis[u] = 1;
q2.emplace(u, w);
}
}
while(!q2.empty()) {
auto [v, f] = q2.front(); q2.pop();
infof("===== BFS2: visiting %d =====", v + 1);
for(auto [u, w]: adj[v]) {
if(dg[u] == 2) continue;
ok[w][0] |= ok[f][1];
ok[w][1] |= ok[f][0];
if(vis[u]) continue;
vis[u] = 1;
q2.emplace(u, w);
}
}
int L = 0, R = 0;
vector<int> A(2 * N);
for(int i = 0; i < 2 * N; ++i) {
auto [u, v] = ed[i];
auto w = W[i];
infof("%d: vis[u] = %d | vis[v] = %d | ok[i] = {%d, %d}",
i + 1, (int)vis[u], (int)vis[v], (int)ok[i][0], (int)ok[i][1]);
if(!vis[u] && !vis[v]) {
V.emplace_back(w);
continue;
}
if(ok[i][0] && ok[i][1] || ok[i][0] && A[v] || ok[i][1] && A[u]) {
cout << "NO" << lf;
return 0;
}
if(!ok[i][0] && !ok[i][1]) continue;
if(ok[i][0]) {
R += w, A[v] = w;
} else L += w, A[u] = w;
}
infof("L = %d | R = %d", L, R);
infor("w:");
for(auto x: V) {
infor(" %d", x);
}
infof("");
int s = 0;
bitset<MAXN> kp; kp[0] = 1;
for(auto w: V) {
s += w;
kp |= kp << w;
}
int mn = INT_MAX;
for(int i = 0; i <= s; ++i) {
if(!kp[i]) continue;
mn = min(mn, abs((L + i) - (R + s - i)));
}
if(mn <= K) {
cout << "YES" << lf;
} else cout << "NO" << lf;
infof("mn = %d | K = %d", mn, K);
}
컴파일 시 표준 에러 (stderr) 메시지
tug.cpp:1:1: error: expected unqualified-id before '>' token
1 | >
| ^
tug.cpp:27:13: error: 'pair' does not name a type
27 | using pll = pair<ll, ll>;
| ^~~~
tug.cpp:28:13: error: 'pair' does not name a type
28 | using pii = pair<int, int>;
| ^~~~
tug.cpp: In function 'int main()':
tug.cpp:35:5: error: 'ios' has not been declared
35 | ios::sync_with_stdio(0);
| ^~~
tug.cpp:36:5: error: 'cin' was not declared in this scope
36 | cin.tie(0); cout.tie(0);
| ^~~
tug.cpp:36:17: error: 'cout' was not declared in this scope
36 | cin.tie(0); cout.tie(0);
| ^~~~
tug.cpp:40:12: error: 'pii' was not declared in this scope
40 | vector<pii> ed(2 * N);
| ^~~
tug.cpp:40:5: error: 'vector' was not declared in this scope
40 | vector<pii> ed(2 * N);
| ^~~~~~
tug.cpp:40:17: error: 'ed' was not declared in this scope
40 | vector<pii> ed(2 * N);
| ^~
tug.cpp:41:12: error: expected primary-expression before 'int'
41 | vector<int> W(2 * N), dg(2 * N);
| ^~~
tug.cpp:42:25: error: 'adj' was not declared in this scope
42 | vector<vector<pii>> adj(2 * N);
| ^~~
tug.cpp:46:26: error: 'W' was not declared in this scope
46 | cin >> u >> v >> W[i];
| ^
tug.cpp:52:9: error: 'dg' was not declared in this scope
52 | dg[u] += 1;
| ^~
tug.cpp:56:5: error: 'queue' was not declared in this scope
56 | queue<int> q;
| ^~~~~
tug.cpp:56:11: error: expected primary-expression before 'int'
56 | queue<int> q;
| ^~~
tug.cpp:58:12: error: 'dg' was not declared in this scope
58 | if(dg[i] == 1) q.emplace(i);
| ^~
tug.cpp:58:24: error: 'q' was not declared in this scope
58 | if(dg[i] == 1) q.emplace(i);
| ^
tug.cpp:63:12: error: 'q' was not declared in this scope
63 | while(!q.empty()) {
| ^
tug.cpp:67:13: error: 'dg' was not declared in this scope
67 | dg[u] -= 1;
| ^~
tug.cpp:75:17: error: 'dg' was not declared in this scope
75 | for(auto x: dg) {
| ^~
tug.cpp:80:12: error: expected primary-expression before 'bool'
80 | vector<bool> vis(2 * N);
| ^~~~
tug.cpp: In lambda function:
tug.cpp:82:12: error: 'vis' was not declared in this scope
82 | if(vis[v]) return 0;
| ^~~
tug.cpp:83:9: error: 'vis' was not declared in this scope
83 | vis[v] = 1;
| ^~~
tug.cpp:89:26: error: 'dg' was not declared in this scope
89 | if(w == f || dg[u] < 2) continue;
| ^~
tug.cpp:98:20: error: 'W' was not declared in this scope
98 | return W[w] - x;
| ^
tug.cpp:101:9: error: there are no arguments to 'assert' that depend on a template parameter, so a declaration of 'assert' must be available [-fpermissive]
101 | assert(0);
| ^~~~~~
tug.cpp:101:9: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
tug.cpp: In function 'int main()':
tug.cpp:104:12: error: expected primary-expression before 'int'
104 | vector<int> V;
| ^~~
tug.cpp:106:12: error: 'dg' was not declared in this scope
106 | if(dg[i] < 2) continue;
| ^~
tug.cpp:110:15: error: 'V' was not declared in this scope
110 | if(x) V.emplace_back(abs(x));
| ^
tug.cpp:110:30: error: 'abs' was not declared in this scope
110 | if(x) V.emplace_back(abs(x));
| ^~~
tug.cpp:113:12: error: 'array' was not declared in this scope
113 | vector<array<bool, 2>> ok(2 * N);
| ^~~~~
tug.cpp:113:18: error: expected primary-expression before 'bool'
113 | vector<array<bool, 2>> ok(2 * N);
| ^~~~
tug.cpp:115:16: error: 'q2' was not declared in this scope
115 | queue<pii> q2;
| ^~
tug.cpp:117:13: error: 'vis' was not declared in this scope
117 | if(!vis[i]) continue;
| ^~~
tug.cpp:121:16: error: 'dg' was not declared in this scope
121 | if(dg[u] == 2) continue;
| ^~
tug.cpp:123:13: error: 'ok' was not declared in this scope; did you mean 'k'?
123 | ok[w][k] = 1;
| ^~
| k
tug.cpp:125:16: error: 'vis' was not declared in this scope
125 | if(vis[u]) continue;
| ^~~
tug.cpp:126:13: error: 'vis' was not declared in this scope
126 | vis[u] = 1;
| ^~~
tug.cpp:138:16: error: 'dg' was not declared in this scope
138 | if(dg[u] == 2) continue;
| ^~
tug.cpp:140:13: error: 'ok' was not declared in this scope
140 | ok[w][0] |= ok[f][1];
| ^~
tug.cpp:143:16: error: 'vis' was not declared in this scope
143 | if(vis[u]) continue;
| ^~~
tug.cpp:144:13: error: 'vis' was not declared in this scope
144 | vis[u] = 1;
| ^~~
tug.cpp:151:12: error: expected primary-expression before 'int'
151 | vector<int> A(2 * N);
| ^~~
tug.cpp:154:18: error: 'W' was not declared in this scope
154 | auto w = W[i];
| ^
tug.cpp:159:13: error: 'vis' was not declared in this scope
159 | if(!vis[u] && !vis[v]) {
| ^~~
tug.cpp:160:13: error: 'V' was not declared in this scope
160 | V.emplace_back(w);
| ^
tug.cpp:164:12: error: 'ok' was not declared in this scope
164 | if(ok[i][0] && ok[i][1] || ok[i][0] && A[v] || ok[i][1] && A[u]) {
| ^~
tug.cpp:164:48: error: 'A' was not declared in this scope
164 | if(ok[i][0] && ok[i][1] || ok[i][0] && A[v] || ok[i][1] && A[u]) {
| ^
tug.cpp:169:13: error: 'ok' was not declared in this scope
169 | if(!ok[i][0] && !ok[i][1]) continue;
| ^~
tug.cpp:171:12: error: 'ok' was not declared in this scope
171 | if(ok[i][0]) {
| ^~
tug.cpp:172:21: error: 'A' was not declared in this scope
172 | R += w, A[v] = w;
| ^
tug.cpp:173:24: error: 'A' was not declared in this scope
173 | } else L += w, A[u] = w;
| ^
tug.cpp:178:17: error: 'V' was not declared in this scope
178 | for(auto x: V) {
| ^
tug.cpp:184:5: error: 'bitset' was not declared in this scope
184 | bitset<MAXN> kp; kp[0] = 1;
| ^~~~~~
tug.cpp:184:18: error: 'kp' was not declared in this scope
184 | bitset<MAXN> kp; kp[0] = 1;
| ^~
tug.cpp:185:17: error: 'V' was not declared in this scope
185 | for(auto w: V) {
| ^
tug.cpp:190:14: error: 'INT_MAX' was not declared in this scope
190 | int mn = INT_MAX;
| ^~~~~~~
tug.cpp:1:1: note: 'INT_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
+++ |+#include <climits>
1 | >
tug.cpp:194:22: error: 'abs' was not declared in this scope
194 | mn = min(mn, abs((L + i) - (R + s - i)));
| ^~~
tug.cpp:194:14: error: 'min' was not declared in this scope; did you mean 'mn'?
194 | mn = min(mn, abs((L + i) - (R + s - i)));
| ^~~
| mn
tug.cpp: In instantiation of 'main()::<lambda(int, int, auto:1&&)> [with auto:1 = main()::<lambda(int, int, auto:1&&)>&]':
tug.cpp:108:20: required from here
tug.cpp:101:15: error: 'assert' was not declared in this scope
101 | assert(0);
| ~~~~~~^~~
tug.cpp:1:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
+++ |+#include <cassert>
1 | >