Submission #656394

#	Time	Username	Problem	Language	Result	Execution time	Memory
656394		cadmiumsky	Graph (BOI20_graph)	C++14	0 / 100	2 ms	2656 KiB

Graph

#include <bits/stdc++.h>

using namespace std;
const int nmax = 1e5 + 5;
using pii = pair<int,int>;
using ll = long long;

//int attempt = 0; 
vector<pii> g[nmax];
vector<int> atr, atrsg;
vector<int> col;
int current;

void dfs(int node, int with, int c, int bw) {
  col[node] = c;
  //cerr << node << ' ' << c << '\t' << with << ' ' << bw << '\n';
  if(atr[node] != nmax * 4) {
    if(bw != atrsg[node]) {
      int cnd = (atr[node] - with) / (bw * 2);
      //cerr << cnd << '\n';
      if(current == nmax * 4 || current == cnd)
	current = cnd;
      else current = -nmax * 4;
    }
    else if(atr[node] != with)
      current = -nmax * 4;
    return;
  }
  atrsg[node] = bw;
  atr[node] = with;
  bool ok = 1;
  for(auto [x, cap] : g[node]) {
    dfs(x, cap - with, c, -bw);
  }
  return;
} 
int n, m;

void initv(vector<int>& x) {
  x.clear();
  x.resize(n + 1, nmax * 4);
}

vector<int> attempt() {
  initv(col);
  initv(atr);
  initv(atrsg);
  bool ok = 1;
  vector<int> atrcol;
  int flag = 1;
  for(int i = 1; i <= n; i++) {
    if(atr[i] == nmax * 4) {
      current = nmax * 4;
      dfs(i, 0, flag, 1);
      //cerr << '\n';
      if(current == -nmax * 4)
	return vector<int>();
      else if(current == nmax * 4)
	current = 0;
      atrcol.push_back(current);
      flag++;
    }
  }
  
  vector<int> rez;
  for(int i = 1; i <= n; i++)
    rez.emplace_back(atrsg[i] * atrcol[col[i] - 1] + atr[i]);
  return rez;
}

ll getsum(vector<int>& x) {
  ll sum = 0;
  for(auto a : x) sum += abs(a);
  return sum;
}

int main() {
  cin >> n >> m;
  for(int i = 0, x, y, c; i < m; i++) {
    cin >> x >> y >> c;
    g[x].emplace_back(y, c * 2);
    g[y].emplace_back(x, c * 2);
  }

  vector<int> rez = attempt();
  if(rez.empty()) cout << "NO\n";
  else {
    cout << "YES\n";
    for(auto x : rez) {
      if(x < 0)	
	cout << "-", x = abs(x);
      cout << x / 2;
      if(x % 2) cout << ".5";
      cout << ' ';
    }
    cout << '\n';
  }
}

Compilation message (stderr)

Graph.cpp: In function 'void dfs(int, int, int, int)':
Graph.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |   for(auto [x, cap] : g[node]) {
      |            ^
Graph.cpp:31:8: warning: unused variable 'ok' [-Wunused-variable]
   31 |   bool ok = 1;
      |        ^~
Graph.cpp: In function 'std::vector<int> attempt()':
Graph.cpp:48:8: warning: unused variable 'ok' [-Wunused-variable]
   48 |   bool ok = 1;
      |        ^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42