| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 652430 |
2022-10-22T15:11:46 Z |
1zaid1 |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
2700 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';
const int M = 1e5+5, MOD = 1e9+7;
int p[M], d[M], loop, vis[M], f[M];
vector<pair<int, int>> node[M];
bitset<100005> is;
vector<int> tmp;
double cost[M];
void dfs(int s, int dp = 0) {
vis[s] = 1;
d[s] = dp++;
tmp.push_back(s);
for (auto [i, x]:node[s]) {
if (!vis[i]) {
p[i] = s;
dfs(i, dp);
} else if (!loop && (dp-d[i])%2) {
loop = s;
p[i] = s;
}
}
}
double eval(int s, double a, int cnt = 0) {
double ans = abs(a);
cost[s] = a;
is[s] = 1;
for (auto [i, x]:node[s]) {
if (!is[i]) ans += abs(eval(i, x-a));
} return ans;
}
bool check(vector<int> v) {
for (int y:v) {
for (auto [i, x]:node[y]) {
if (abs(cost[y] + cost[i]-x) >= 1e-6) return 0;
}
} return true;
}
void dfs2(int s, int d = 0) {
vis[s] = true;
for (auto [i, x]:node[s]) {
if (!vis[i]) {
f[i] = f[s]+(d?x:-x);
dfs2(i, !d);
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
map<pair<int, int>, int> ed;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a > b) swap(a, b);
if (ed[{a, b}] && ed[{a, b}] != c) {
cout << "NO" << endl;
return 0;
} else if (ed[{a, b}]) continue;
ed[{a, b}] = ed[{b, a}] = c;
node[a].push_back({b, c});
node[b].push_back({a, c});
}
for (int k = 1; k <= n; k++) {
if (!vis[k] && node[k].size()) {
dfs(k);
if (loop) {
vector<int> lp = {loop};
for (int x = p[loop]; x != loop; x = p[x]) lp.push_back(x);
lp.push_back(loop);
double sum = 0;
for (int i = 0, f = 1; i < lp.size()-1; i++, f ^= 1) {
if (f) sum += ed[{min(lp[i], lp[i+1]), max(lp[i], lp[i+1])}];
else sum -= ed[{min(lp[i], lp[i+1]), max(lp[i], lp[i+1])}];
}
eval(loop, sum/2);
} else {
eval(k, 0);
if (!check(tmp)) {
cout << "NO" << endl;
return 0;
}
// int l = -n-1, r = n+1, cnt = 0;
// while (cnt++<60) {
// int ll = (2*l+r)/3;
// int rr = (l+2*r)/3;
// is = 0; double x = eval(k, ll);
// is = 0; double y = eval(k, rr);
// if (x >= y) l = ll;
// else r = rr;
// } is = 0; eval(k, (l+r)/2);
is = 0;
dfs2(k);
map<int, int> fr, ir;
for (int i:tmp) fr[f[i]]++;
for (int i:tmp) ir[f[i]] = i;
int sum = 0;
for (auto [a, b]:fr) sum += a*b;
vector<int> nor; for (int i:tmp) nor.push_back(f[i]);
sort(nor.begin(), nor.end());
vector<int> pre = {0}; for (int i:nor) pre.push_back(pre.back()+i);
int ans = 1, mn = INT_MAX;
for (int i:tmp) {
int a = -f[i];
int num = upper_bound(nor.begin(), nor.end(), -a)-nor.begin();
int x = pre[num];
int val = (sum - x)+(n-num)*a -(a*num + x);
if (val < mn) ans = i;
mn = min(mn, val);
// cout << i << ' ' << val << endl;
}
is = 0;
eval(ans, 0);
}
if (!check(tmp)) {
cout << "NO" << endl;
return 0;
}
tmp = {};
loop = 0;
}
}
cout << "YES" << fixed << setprecision(6) << endl;
for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
return 0;
}
/*
3 3
1 1 2
2 2 1
2 3 2
4 5
1 4 2
3 2 1
2 1 2
3 4 1
1 3 2
4 4
1 2 1
2 3 2
1 3 2
3 4 1
*/
Compilation message
Graph.cpp: In function 'int main()':
Graph.cpp:86:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0, f = 1; i < lp.size()-1; i++, f ^= 1) {
| ~~^~~~~~~~~~~~~
Graph.cpp:147:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
147 | for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
| ^~~
Graph.cpp:147:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
147 | for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2692 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 4 |
Correct |
2 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2692 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 4 |
Correct |
2 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2692 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 4 |
Correct |
2 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2692 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 4 |
Correct |
2 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2644 KB |
answer = YES |
| 2 |
Correct |
2 ms |
2692 KB |
answer = YES |
| 3 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 4 |
Correct |
2 ms |
2644 KB |
answer = NO |
| 5 |
Correct |
2 ms |
2700 KB |
answer = YES |
| 6 |
Incorrect |
2 ms |
2644 KB |
participant answer is larger than the answer of jury |
| 7 |
Halted |
0 ms |
0 KB |
- |
