Submission #1168558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168558		ElayV13	Graph (BOI20_graph)	C++20	34 / 100	46 ms	5960 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MXN = 100005;
const int INF = 1e18;

int n , m , u[MXN] , v[MXN] , c[MXN] , com[MXN] , cur_com = 0 , f = 0;
vector < pair < int , int > > adj[MXN];
bool vis[MXN];
ld valx[MXN] , s = 0;

void dfs(int v)
{
        com[v] = cur_com;
        vis[v] = 1;
        for(pair < int , int > u : adj[v])
        {
                if(!vis[u.first])
                {
                        dfs(u.first);
                }
        }
}

vector < vector < int > > comp;

vector < bool > used(MXN , false);

vector < ld > res(MXN , -1);

vector < int > nodes;

void init(int n){
        nodes.clear();
        f = s = 0;
        for(int i = 1;i <= n;i++) valx[i] = -100 , used[i] = 0;
}

void calc(int node)
{
        nodes.push_back(node);
        used[node] = 1;
        s += abs(valx[node]);
        for(pair < int , int > u : adj[node])
        {
                int color = u.second;
                int v = u.first;
                if(!used[v])
                {
                        valx[v] = ((color == 2) ? (2 - valx[node]) : (1 - valx[node]));
                        calc(v);
                }
                else
                {
                        int req = ((color == 2) ? 2 : 1);
                        if(valx[v] + valx[node] != req)
                        {
                                f = 1;
                        }
                }
        }
}

signed main(){
      ios_base::sync_with_stdio(0);cin.tie(0);
      cin >> n >> m;
      for(int i = 1;i <= m;i++)
      {
              cin >> u[i] >> v[i] >> c[i];
              adj[u[i]].push_back({v[i] , c[i]});
              adj[v[i]].push_back({u[i] , c[i]});
      }
      for(int i = 1;i <= n;i++)
      {
              if(!vis[i])
              {
                      ++cur_com;
                      dfs(i);
              }
      }
      comp.resize(cur_com + 1);
      for(int i = 1;i <= n;i++)
      {
              comp[com[i]].push_back(i);
      }
      for(int i = 0;i < comp.size();i++)
      {
              if(!comp[i].size()) continue;
              int node = comp[i][0];
              int cnt = 0;
              ld mn = INF;
              for(int val = -70;val <= 70;val++)
              {
                      ld db_val = val;
                      init(n);
                      valx[node] = db_val / 10;
                      calc(node);
                      cnt += !f;
                      if(!f)
                      {
                              if(s < mn)
                              {
                                      for(int v : nodes) res[v] = valx[v];
                                      mn = s;
                              }
                      }
              }
              if(!cnt)
              {
                      cout << "NO" << endl;
                      return 0;
              }
      }
      cout << "YES" << "\n";
      for(int i = 1;i <= n;i++)
      {
              cout << res[i] << ' ';
      }
      cout << "\n";
}

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