Submission #34311054

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

struct Rule {
  int trigger;
  int limit;
  int who;

  bool operator<(const Rule &other) const {
    return trigger < other.trigger;
  }
};

int n, m, k, p, x, q, y;
vector<vector<Rule>> rules;
vector<int> v;
vector<int> executed;
queue< pair<int, int> > que;

void advance(int pos) {
  while (executed[pos] < rules[pos].size() && rules[pos][executed[pos]].trigger < v[pos]) {
    Rule rule = rules[pos][executed[pos]++];
   
    if (v[rule.who] < rule.limit + 1) {
      v[rule.who] = rule.limit + 1;
      que.push(make_pair(v[rule.who], rule.who));
    }
  }

  int aux = executed[pos];
  while (aux < rules[pos].size() && rules[pos][aux].trigger == v[pos]) {
    Rule rule = rules[pos][aux++];
   
    if (v[rule.who] < rule.limit) {
      v[rule.who] = rule.limit;
      que.push(make_pair(v[rule.who], rule.who));
    }
  }
}

void check_rule(int pos, Rule rule) {
  int p, q, x, y;
  bool bad = false;
  p = pos; q = rule.who;
  x = rule.trigger; y = rule.limit;

  bad |= v[p] < x && !(v[q] < y);
  bad |= v[p] == x && !(v[q] == y);
  bad |= v[p] > x && !(v[q] > y);

  if (bad) {
    cout << -1;
    exit(0);
  }
}

int main()
{
  cin >> n >> m >> k;

  rules.resize(n);
  v.resize(n);
  executed.resize(n);

  for (int i = 0; i < k; i++) {
    cin >> p >> x >> q >> y;
    p--; x--;
    q--; y--;

    rules[p].push_back({
      .trigger = x,
      .limit = y,
      .who = q
    });

    rules[q].push_back({
      .trigger = y,
      .limit = x,
      .who = p
    });
  }

  for (int i = 0; i < n; i++) 
    sort(rules[i].begin(), rules[i].end());

  for (int i = 0; i < n; i++) {
    v[i] = 0;
    executed[i] = 0;
    que.push(make_pair(0, i));
  }

  while (!que.empty()) {
    pair<int, int> curr = que.front(); que.pop();
    int val = curr.first;
    int pos = curr.second;

    if (v[pos] != val) continue;
    advance(pos);
  }
 
  ll ans = n;
  for (int i = 0; i < n; i++) {
    ans += v[i];

    if (v[i] >= m) {
      cout << -1;
      return 0;
    }

    for (Rule rule: rules[i]) 
      check_rule(i, rule);
  }

  cout << ans;


  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void advance(int)’:
./Main.cpp:32:24: warning: comparison of integer expressions of different signedness: ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} and ‘std::vector<Rule>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   32 |   while (executed[pos] < rules[pos].size() && rules[pos][executed[pos]].trigger < v[pos]) {
./Main.cpp:42:14: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<Rule>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   42 |   while (aux < rules[pos].size() && rules[pos][aux].trigger == v[pos]) {
      |          ~~~~^~~~~~~~~~~~~~~~~~~

Judge Result