Submission #1012691

#TimeUsernameProblemLanguageResultExecution timeMemory
1012691LucaIlieGraph (BOI20_graph)C++17
0 / 100
6 ms9820 KiB
#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(type[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()); //for( j = 0; j < v.size(); j++ ) // cout << v[j] << " "; //cout << "\n"; modificat[find_daddy(i)] = -v[(v.size() + 1)/ 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 (stderr)

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:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for( j = 0; j < edges[i].size(); j++ ) {
      |                     ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...