제출 #793176

#제출 시각아이디문제언어결과실행 시간메모리
793176peijarGraph (BOI20_graph)C++17
100 / 100
107 ms16892 KiB
#include <iostream> #include <fstream> #include <cstdio> #include <iomanip> #include <sstream> #include <cstring> #include <string> #include <cmath> #include <stack> #include <list> #include <queue> #include <deque> #include <set> #include <map> #include <vector> #include <algorithm> #include <numeric> #include <utility> #include <functional> #include <limits> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<int,int> pii; typedef vector<vector<int> > graph; const double pi = acos(-1.0); #define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; } #define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } } #define mp make_pair #define pb push_back #define fst first #define snd second const int MAXN = 200005; int n, m; vector<pii> g[MAXN]; int vis[MAXN]; int sgn[MAXN]; int val[MAXN]; queue<int> Q; int ans[MAXN]; int cnt; int comp[MAXN]; int num[MAXN]; void solve() { memset(vis,0,sizeof(vis)); for(int u = 1; u <= n; u++) { if(!vis[u]) { vis[u] = true; sgn[u] = +1; val[u] = 0; cnt = 0; comp[cnt++] = u; bool bip = true; double x; Q.push(u); while(!Q.empty()) { int v = Q.front(); Q.pop(); for(size_t i = 0; i < g[v].size(); i++) { int w = g[v][i].fst; int sum = g[v][i].snd; if(!vis[w]) { vis[w] = true; sgn[w] = -sgn[v]; val[w] = sum-val[v]; comp[cnt++] = w; Q.push(w); } else if(sgn[w]==sgn[v]) { bip = false; x = sgn[w]*(sum-val[w]-val[v])/2; } } } if(bip) { for(int i = 0; i < cnt; i++) { int v = comp[i]; num[i] = (-sgn[v])*val[v]; } sort(num,num+cnt); x = num[cnt/2]; } for(int i = 0; i < cnt; i++) { int v = comp[i]; ans[v] = val[v] + sgn[v]*x; } for(int i = 0; i < cnt; i++) { int v = comp[i]; for(size_t i = 0; i < g[v].size(); i++) { int w = g[v][i].fst; if(ans[v]+ans[w]!=g[v][i].snd) { printf("NO\n"); return; } } } } } printf("YES\n"); for(int v = 1; v <= n; v++) { printf("%.1lf ", 0.5*ans[v]); } printf("\n"); } int main() { //freopen("input.in", "r", stdin); //freopen("output.out", "w", stdout); while(scanf("%d %d", &n, &m)==2) { for(int i = 1; i <= n; i++) { g[i].clear(); } for(int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); c *= 2; g[a].pb(mp(b,c)); g[b].pb(mp(a,c)); } solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

Graph.cpp: In function 'int main()':
Graph.cpp:128:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |    int a, b, c; scanf("%d %d %d", &a, &b, &c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...