이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int n, k, pre[120005], vis[120005], match[120005], cnt;
bitset<30000 * 20 * 4> b, bb;
vector<pii> E[120005], T[120005];
pair<pii, int> nT;
vector<int> cV;
bool valid = 1;
void dfs(int u)
{
cnt += (u <= 2 * n ? 1 : -1);
cV.emplace_back(u);
vis[u] = 1;
for (auto [v, w] : E[u])
if (!vis[v])
{
T[u].emplace_back(pii(v, w));
pre[v] = u;
dfs(v);
}
else if (v != pre[u])
nT = make_pair(pii(u, v), w);
}
int matching(int u)
{
int tot = 0;
for (auto [v, w] : T[u])
{
tot += matching(v);
if (!match[u] && !match[v])
match[u] = match[v] = 1, tot += w;
}
return tot;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= 2 * n; i++)
{
int l, r, w;
cin >> l >> r >> w;
E[i].emplace_back(pii(2 * n + l, w));
E[2 * n + l].emplace_back(pii(i, w));
E[i].emplace_back(pii(3 * n + r, -w));
E[3 * n + r].emplace_back(pii(i, -w));
}
b[40 * n + 1] = 1;
for (int i = 1; i <= 2 * n; i++)
if (!vis[i])
{
cV.clear();
dfs(i);
if (cnt != 0)
{
cout << "NO\n";
cerr << "there is no perfect matching (vertex)\n";
return 0;
}
vector<int> sol;
bool mvalid = 1;
int res = matching(i);
for (auto j : cV)
{
mvalid &= match[j];
match[j] = 0;
}
if (mvalid)
sol.emplace_back(res);
match[nT.F.F] = match[nT.F.S] = 1;
mvalid = 1;
res = nT.S + matching(i);
for (auto j : cV)
mvalid &= match[j];
if (mvalid)
sol.emplace_back(res);
if (sol.size() == 0)
{
cout << "NO\n";
cerr << "there is no perfect matching (dfs)\n";
return 0;
}
bb = 0;
for (auto j : sol)
{
if (j < 0)
bb = bb | b >> (-j);
else
bb = bb | b << j;
}
b = bb;
}
for (int i = 40 * n + 1 - k; i <= 40 * n + 1 + k; i++)
if (b[i])
{
cout << "YES\n";
return 0;
}
cout << "NO\n";
cerr << "k is too small\n";
}
컴파일 시 표준 에러 (stderr) 메시지
tug.cpp: In function 'void dfs(int)':
tug.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | for (auto [v, w] : E[u])
| ^
tug.cpp: In function 'int matching(int)':
tug.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | for (auto [v, w] : T[u])
| ^
# | 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... |