| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1012669 |
2024-07-02T13:32:41 Z |
LucaIlie |
Graph (BOI20_graph) |
C++17 |
|
2 ms |
10328 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 100001
vector <int> edges[nmax], price[nmax], arbore[nmax], pricearb[nmax], v;
int daddy[nmax], type[nmax], paritate[nmax], comp[nmax], muchii[nmax];
double modificat[nmax];
const int inf = 1e8;
int find_daddy( int a ) {
int x;
if( daddy[a] == a )
return a;
x = find_daddy(daddy[a]);
daddy[a] = x;
return x;
}
void marry_daddy( int a, int b ) {
int x, y;
x = find_daddy( a );
y = find_daddy( b );
daddy[x] = y;
}
void dfs( int vf, int parent ) {
int i, fiu;
v.push_back(vf * paritate[vf]);
comp[find_daddy(vf)]++;
muchii[find_daddy(vf)] += edges[vf].size();
//cout << vf << "\n";
for( i = 0; i < arbore[vf].size(); i++ ) {
fiu = arbore[vf][i];
if( fiu == parent )
continue;
type[fiu] = pricearb[vf][i] - type[vf];
paritate[fiu] = -paritate[vf];
//cout << fiu << " " << type[fiu] << " " << pricearb[vf][i] << " " << type[vf] << "\n";
dfs( fiu, vf );
}
}
void afisare( int x ) {
if( (x + inf) % 2 == 0 )
cout << x / 2 << " ";
else
cout << (x - 1) / 2 << ".5 ";
}
int main() {
int n, m, i, a, b, c, j;
bool ok = true;
cin >> n >> m;
for( i = 1; i <= n; i++ )
daddy[i] = i;
for( i = 0; i < m; i++ ) {
cin >> a >> b >> c;
edges[a].push_back( b );
edges[b].push_back( a );
price[a].push_back( c );
price[b].push_back( c );
if( find_daddy(a) != find_daddy(b) ) {
marry_daddy( a, b );
arbore[a].push_back(b);
arbore[b].push_back(a);
pricearb[a].push_back(c);
pricearb[b].push_back(c);
}
}
for( i = 1; i <= n; i++ ) {
if( find_daddy(i) == i ) {
paritate[i] = 1;
dfs( i, 0 );
if( 2 * comp[i] == muchii[i] + 2 ) {
//cout << ".";
sort(v.begin(), v.end());
modificat[find_daddy(i)] = -v[v.size() / 2];
}
v.clear();
}
}
//for( i = 1; i <= n; i++ )
// cout << type[i] << " ";
for( i = 1; i <= n; i++ ) {
for( j = 0; j < edges[i].size(); j++ ) {
if( type[i] + type[edges[i][j]] + (paritate[i] + paritate[edges[i][j]]) * modificat[find_daddy(i)] != price[i][j] ) {
if( modificat[find_daddy(i)] == 0 && paritate[i] == paritate[edges[i][j]] )
modificat[find_daddy(i)] = (((double)price[i][j] - type[i] - type[edges[i][j]]) / 2) * paritate[i];
else ok = false;
}
}
}
//cout << "\n";
//for( i = 1; i <= n; i++ )
// cout << type[i] + paritate[i] * modificat[find_daddy(i)] << " ";
if( !ok ) {
cout << "NO\n";
return 0;
}
cout << "YES\n";
for( i = 1; i <= n; i++ )
cout << type[i] + paritate[i] * modificat[find_daddy(i)] << " ";
return 0;
}
Compilation message
Graph.cpp: In function 'void dfs(int, int)':
Graph.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for( i = 0; i < arbore[vf].size(); i++ ) {
| ~~^~~~~~~~~~~~~~~~~~~
Graph.cpp: In function 'int main()':
Graph.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for( j = 0; j < edges[i].size(); j++ ) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10328 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
9816 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10328 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
9816 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10328 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
9816 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10328 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
9816 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10328 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
9816 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
