| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726405 |
2023-04-18T21:11:05 Z |
YENGOYAN |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
340 KB |
/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <algorithm>
#include <bitset>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;
vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };
void solve() {
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> gp(n);
for(int i = 0; i < m; ++i){
LL u, v, w; cin >> u >> v >> w; w *= 10;
gp[--u].push_back({--v, w});
gp[v].push_back({u, w});
}
vector<LL> ans(n, inf);
vector<LL> val(n);
vector<bool> vis;
LL sm = 0;
vector<int> comp;
function<void(int)> dfs = [&](int u){
if(sm == inf) {
return;
}
sm += abs(val[u]);
comp.push_back(u);
vis[u] = 1;
for(pair<int, int> &v : gp[u]) {
if(!vis[v.first]) {
val[v.first] = v.second - val[u];
dfs(v.first);
}
else if(val[u] + val[v.first] != v.second) {
sm = inf;
return;
}
}
};
vector<double> res(n);
vector<int> st;
for(int a = -1000; a <= 1000; ++a){
vis = vector<bool> (n);
val = vector<LL> (n);
for(int i = 0; i < n; ++i) {
if(vis[i]) {
continue;
}
st.push_back(i);
sm = 0;
val[i] = a;
comp.clear();
dfs(i);
if(sm < ans[i]) {
ans[i] = sm;
for(int &u : comp) {
res[u] = val[u];
}
}
}
}
for(int &u : st){
if(ans[u] == inf){
cout << "NO\n";
return;
}
}
cout << "YES\n";
for(int i = 0; i < n; ++i) {
cout << double(res[i] / 10) << " ";
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int t; cin >> t; while(t--)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
answer = YES |
| 2 |
Correct |
1 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Correct |
1 ms |
340 KB |
answer = NO |
| 5 |
Correct |
1 ms |
340 KB |
answer = YES |
| 6 |
Correct |
1 ms |
212 KB |
answer = YES |
| 7 |
Correct |
1 ms |
212 KB |
answer = YES |
| 8 |
Correct |
1 ms |
212 KB |
answer = YES |
| 9 |
Correct |
1 ms |
212 KB |
answer = NO |
| 10 |
Correct |
1 ms |
212 KB |
answer = YES |
| 11 |
Correct |
1 ms |
212 KB |
answer = YES |
| 12 |
Correct |
1 ms |
212 KB |
answer = NO |
| 13 |
Incorrect |
1 ms |
340 KB |
jury has the better answer: jans = YES, pans = NO |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
answer = YES |
| 2 |
Correct |
1 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Correct |
1 ms |
340 KB |
answer = NO |
| 5 |
Correct |
1 ms |
340 KB |
answer = YES |
| 6 |
Correct |
1 ms |
212 KB |
answer = YES |
| 7 |
Correct |
1 ms |
212 KB |
answer = YES |
| 8 |
Correct |
1 ms |
212 KB |
answer = YES |
| 9 |
Correct |
1 ms |
212 KB |
answer = NO |
| 10 |
Correct |
1 ms |
212 KB |
answer = YES |
| 11 |
Correct |
1 ms |
212 KB |
answer = YES |
| 12 |
Correct |
1 ms |
212 KB |
answer = NO |
| 13 |
Incorrect |
1 ms |
340 KB |
jury has the better answer: jans = YES, pans = NO |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
answer = YES |
| 2 |
Correct |
1 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Correct |
1 ms |
340 KB |
answer = NO |
| 5 |
Correct |
1 ms |
340 KB |
answer = YES |
| 6 |
Correct |
1 ms |
212 KB |
answer = YES |
| 7 |
Correct |
1 ms |
212 KB |
answer = YES |
| 8 |
Correct |
1 ms |
212 KB |
answer = YES |
| 9 |
Correct |
1 ms |
212 KB |
answer = NO |
| 10 |
Correct |
1 ms |
212 KB |
answer = YES |
| 11 |
Correct |
1 ms |
212 KB |
answer = YES |
| 12 |
Correct |
1 ms |
212 KB |
answer = NO |
| 13 |
Incorrect |
1 ms |
340 KB |
jury has the better answer: jans = YES, pans = NO |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
answer = YES |
| 2 |
Correct |
1 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Correct |
1 ms |
340 KB |
answer = NO |
| 5 |
Correct |
1 ms |
340 KB |
answer = YES |
| 6 |
Correct |
1 ms |
212 KB |
answer = YES |
| 7 |
Correct |
1 ms |
212 KB |
answer = YES |
| 8 |
Correct |
1 ms |
212 KB |
answer = YES |
| 9 |
Correct |
1 ms |
212 KB |
answer = NO |
| 10 |
Correct |
1 ms |
212 KB |
answer = YES |
| 11 |
Correct |
1 ms |
212 KB |
answer = YES |
| 12 |
Correct |
1 ms |
212 KB |
answer = NO |
| 13 |
Incorrect |
1 ms |
340 KB |
jury has the better answer: jans = YES, pans = NO |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
answer = YES |
| 2 |
Correct |
1 ms |
212 KB |
answer = YES |
| 3 |
Correct |
1 ms |
212 KB |
answer = YES |
| 4 |
Correct |
1 ms |
340 KB |
answer = NO |
| 5 |
Correct |
1 ms |
340 KB |
answer = YES |
| 6 |
Correct |
1 ms |
212 KB |
answer = YES |
| 7 |
Correct |
1 ms |
212 KB |
answer = YES |
| 8 |
Correct |
1 ms |
212 KB |
answer = YES |
| 9 |
Correct |
1 ms |
212 KB |
answer = NO |
| 10 |
Correct |
1 ms |
212 KB |
answer = YES |
| 11 |
Correct |
1 ms |
212 KB |
answer = YES |
| 12 |
Correct |
1 ms |
212 KB |
answer = NO |
| 13 |
Incorrect |
1 ms |
340 KB |
jury has the better answer: jans = YES, pans = NO |
| 14 |
Halted |
0 ms |
0 KB |
- |
