Submission #1235290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235290		radaiosm7	Graph (BOI20_graph)	C++20	100 / 100	244 ms	34992 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, e, a, b, c, center;
vector<pair<int, int> > adj[100005];
map<pair<int, int>, int> m;
bool visited[100005];
vector<int> nodes;
bool gotval[100005];
pair<int, double> val[100005]; // first*c+second
double ans[100005];
double val_decided;
const double eps = 1e-9;
bool ok;

void dfs(int x) {
  nodes.push_back(x);
  visited[x] = true;

  for (auto edge : adj[x]) {
    int y = edge.X;
    if (visited[y]) continue;
    dfs(y);
  }
}

void colour(int x) {
  for (auto edge : adj[x]) {
    int y = edge.X;
    int c = edge.Y;

    if (gotval[y]) {
      if (fabs(val[y].X+val[x].X) > eps || fabs(val[y].Y+val[x].Y-(double)c) > eps) {
        ok = false;
        if (val[x].X+val[y].X == 0) val_decided = 0.0;
        else val_decided = ((double)c-val[x].Y-val[y].Y)/(double)(val[x].X+val[y].X);
        center = y;
      }
    }

    else {
      gotval[y] = true;
      val[y].X = -val[x].X;
      val[y].Y = -val[x].Y+(double)c;
      colour(y);
    }

    if (!ok) break;
  }
}

double cost(double t) {
  double total = 0.0;
  for (auto x : nodes) total += fabs(t*(double)val[x].X+val[x].Y);
  return total;
}

int main() {
  scanf("%d%d", &n, &e);
  for (int i=1; i <= n; ++i) gotval[i] = false;
  for (int i=1; i <= n; ++i) ans[i] = 0;

  for (int i=0; i < e; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    auto p = make_pair(a, b);

    if (m.find(p) != m.end()) {
      if (m[p] != c) {
        printf("NO\n");
        return 0;
      }
    }

    if (a == b) {
      gotval[a] = true;
      val[a] = make_pair(0, (c == 1) ? 0.5 : 1.0);
      ans[a] = (c == 1) ? 0.5 : 1.0;
    }

    m[make_pair(a, b)] = c;
    adj[a].push_back(make_pair(b, c));
    adj[b].push_back(make_pair(a, c));
  }

  for (int i=1; i <= n; ++i) {
    if (!visited[i]) {
      nodes.clear();
      dfs(i);

      if ((int)nodes.size() == 1) continue;
      center = i;

      for (auto y : nodes) {
        if (gotval[y]) {
          center = y;
          break;
        }
      }

      if (!gotval[center]) {
        gotval[center] = true;
        val[center] = make_pair(1, 0);
      }

      ok = true;
      val_decided = -1000000.0;
      colour(center);

      if (!ok) {
        ok = true;
        for (auto x : nodes) gotval[x] = false;
        gotval[center] = true;
        val[center] = make_pair(0, (double)val[center].X*val_decided+val[center].Y);
        colour(center);

        if (!ok) {
          printf("NO\n");
          return 0;
        }

        else {
          for (auto x : nodes) ans[x] = val[x].Y;
          continue;
        }
      }

      double l = -100000;
      double r = 100000;

      while (r-l > eps) {
        double md1 = l+(r-l)/3.0;
        double md2 = r-(r-l)/3.0;

        if (cost(md1) < cost(md2)) r = md2;
        else l = md1;
      }

      for (auto x : nodes) ans[x] = l*(double)val[x].X+val[x].Y;
    }
  }

  printf("YES\n");
  for (int i=1; i <= n; ++i) printf("%.7lf%c", ans[i], (i == n) ? '\n' : ' ');
  return 0;
}

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d%d", &n, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~
Graph.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d%d", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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