글 읽기 - 문제가 풀리지 않아 도움을 요청 드립니다.

pjshwa 2년 전 0

코드가 길지만... 요약을 해보겠습니다.

M개의 합동식 정보를, N개의 배열 원소를 잇는 간선 정보로 생각
모든 배열 원소를 알 수 있는 최소 cost 는, 연결 요소별로 가장 싸게 reveal 할 수 있는 배열 원소의 cost 의 합
연결 요소 안에 cycle 이 존재하지 않을 경우, 가장 싸게 reveal 할 수 있는 배열 원소에 1을 무조건 대입 후 간선별 ci 정보를 통해 나머지를 알아냄
연결 요소 안에 cycle 이 존재할 경우
- 가장 싸게 reveal 할 수 있는 배열 원소의 값을 미지수로 둠 (x 라고 가정)
- 나머지 연결 요소의 원소 값들은, 간선의 ci 정보에 따라 x 를 이용한 식으로 나타낼 수 있음.
  - 하나의 배열 원소의 값이 x 일 경우, 이 원소와 weight (ci) 6 으로 연결된 다른 원소의 값은 6 - x 이다
- 이렇게 원소 값들을 채워 나가는 과정에서 cycle 이 검출될 경우 다음과 같은 방법으로 미지수 값을 알아낸다
  - 미지수 부호가 음수인 원소들끼리 만났을 경우 (예: a - x, b - x) a + b - 2 * x ≡ ci (mod m) 를 만족하는 x 의 값을 후보군으로 지정
  - 미지수 부호가 양수인 원소들끼리 만났을 경우 (예: a + x, b + x) a + b + 2 * x ≡ ci (mod m) 를 만족하는 x 의 값을 후보군으로 지정
  - 미지수 부호가 다른 원소들끼리 만났을 경우 (예: a + x, b - x) a + b ≡ ci (mod m) 를 만족하지 않으면 바로 프로그램 종료, 만족한다면 아무것도 하지 않음
- 위와 같은 방법을 통해 후보군에 속해 있는 원소가 1개 이상 있을 경우 이 값을 가장 싸게 reveal 할 수 있는 배열 원소부터 쭉 대입하고, 없다면 -1 을 출력하고 프로그램을 종료한다.

랜덤 데이터를 생성하여 계속해서 테스트 해보고 있는 중인데, 코드에 어떤 오류가 있는지 모르겠네요. 도와주시면 감사하겠습니다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;

void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}

const int MAX = 2e5;
const ll INF = 1e18;
ll cost[MAX + 1];
ll n, e, m;
vector<pii> graph[MAX + 1];
vector<tii> info;
bool vis[MAX + 1];

ll ccost, cstart;
void dfs(int v) {
  vis[v] = 1;
  if (cost[v] < ccost) {
    ccost = cost[v];
    cstart = v;
  }
  for (auto [d, w] : graph[v]) {
    if (!vis[d]) dfs(d);
  }
}

ll coef[MAX + 1];
bool neg[MAX + 1];
bool has_cycle;
set<ll> candidates;

void dfs_find_candidate(int v, int par, ll cf, bool n) {
  vis[v] = 1;
  coef[v] = cf;
  neg[v] = n;

  for (auto [d, w] : graph[v]) {
    if (vis[d]) {
      if (d == par) continue;

      if (has_cycle == 0) {
        ll av = cf + coef[d];
        if (neg[v] == 1 && neg[d] == 1) {
          has_cycle = 1;
          ll v1 = av + m - w, v2 = av - w;
          for (ll val : {v1, v2}) {
            if (val % 2 == 0) {
              ll ival = val / 2;
              while (ival < 0) ival += m;
              candidates.insert(ival % m);
            }
          }
        }
        else if (neg[v] == 0 && neg[d] == 0) {
          has_cycle = 1;
          ll v1 = w - av + m, v2 = w - av;
          for (ll val : {v1, v2}) {
            if (val % 2 == 0) {
              ll ival = val / 2;
              while (ival < 0) ival += m;
              candidates.insert(ival % m);
            }
          }
        }
        else if (av % m != w % m) {
          cout << "-1\n";
          exit(0);
        }
        else continue;

        // cout << "v: " << v << ", av: " << av << ", d: " << d << ", w: " << w << endl;
        // for (ll e : candidates) cout << e << ' ';
        // cout << '\n';
      }
      else {
        set<ll> ncandidates;
        ll av = cf + coef[d];
        if (neg[v] == 1 && neg[d] == 1) {
          ll v1 = av + m - w, v2 = av - w;
          for (ll val : {v1, v2}) {
            if (val % 2 == 0) {
              ll ival = val / 2;
              while (ival < 0) ival += m;
              ncandidates.insert(ival % m);
            }
          }
        }
        else if (neg[v] == 0 && neg[d] == 0) {
          ll v1 = w - av + m, v2 = w - av;
          for (ll val : {v1, v2}) {
            if (val % 2 == 0) {
              ll ival = val / 2;
              while (ival < 0) ival += m;
              ncandidates.insert(ival % m);
            }
          }
        }
        else if (av % m != w % m) {
          cout << "-1\n";
          exit(0);
        }
        else continue;

        // cout << "v: " << v << ", av: " << av << ", d: " << d << ", w: " << w << endl;
        // for (int e : candidates) cout << e << ' ';
        // cout << '\n';
        // for (int e : ncandidates) cout << e << ' ';
        // cout << '\n';

        set<ll> remove;
        for (auto c : candidates) {
          if (!ncandidates.count(c)) remove.insert(c);
        }
        for (auto c : remove) candidates.erase(c);
      }
    }
    else dfs_find_candidate(d, v, (w + m - cf) % m, !n);
  }
}

bool vism[MAX + 1];
ll pa[MAX + 1];

void dfs_mark(int v, ll val) {
  vism[v] = 1;
  while (val <= 0) val += m;
  pa[v] = val;
  for (auto [d, w] : graph[v]) {
    if (!vism[d]) dfs_mark(d, w - val);
  }
}

void solve() {
  cin >> n >> e >> m;
  for (int i = 1; i <= n; i++) cin >> cost[i];

  for (int i = 0; i < e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    graph[a].push_back({b, c});
    graph[b].push_back({a, c});
    info.push_back({a, b, c});
  }

  ll acost = 0;
  vector<int> spositions;
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      ccost = INF;
      dfs(i);
      acost += ccost;
      spositions.push_back(cstart);
    }
  }

  memset(vis, 0, sizeof vis);
  for (int e : spositions) {
    candidates.clear();
    has_cycle = 0;
    dfs_find_candidate(e, -1, 0, 0);

    if (!has_cycle) dfs_mark(e, 1);
    else if (candidates.size() == 0) return cout << "-1\n", void();
    else dfs_mark(e, *candidates.begin());
  }

  for (auto [a, b, c] : info) {
    if ((pa[a] + pa[b]) % m != c) return cout << "-1\n", void();
  }

  cout << acost << '\n';
  for (int i = 1; i <= n; i++) cout << pa[i] << ' ';
  cout << '\n';
}

int main() {
  fast_io();

  int t = 1;
  // cin >> t;
  while (t--) solve();
}

doju 2년 전 1

x의 후보가 유일하다면 카드를 뒤집을 필요가 없을 것 같습니다.

pjshwa 2년 전 1

그러네요!! doju 님 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제가 풀리지 않아 도움을 요청 드립니다.

pjshwa 2년 전 0

doju 2년 전 1

pjshwa 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말