QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#297754	#4829. Mark on a Graph	fxhd	AC ✓	6ms	4116kb	C++17	3.7kb	2024-01-05 07:28:26	2024-01-05 07:28:27

Judging History

你现在查看的是最新测评结果

[2024-01-05 07:28:27]
评测

测评结果：AC
用时：6ms
内存：4116kb

查看

[2024-01-05 07:28:26]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "debug.hpp"
#else
  #define dbg(...) 0
#endif

template <class T>
void sort_unique(std::vector<T>& v) {
  std::sort(v.begin(), v.end());
  v.resize(std::unique(v.begin(), v.end()) - v.begin());
}

int find_max_clique(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<vector<int>> q;
  for (int i = 0; i < n; ++i) {
    q.emplace_back(1, i);
  }
  int ans = 0;
  vector<int> cnt(n, 0);
  vector<bool> in_clique(n, false);
  vector<int> goods; goods.reserve(n);
  while (!q.empty()) {
    ans++;
    vector<vector<int>> q2;
    for (const vector<int>& cl0 : q) {
      for (int u : cl0) in_clique[u] = true;
      goods.clear();
      for (int u : cl0) {
        for (int v : adj[u]) if (!in_clique[v]) {
          if (++cnt[v] == ans) {
            goods.push_back(v);
          }
        }
      }
      for (int v : goods) {
        vector<int> cl1 = cl0;
        cl1.push_back(v);
        q2.push_back(cl1);
      }
      for (int u : cl0) {
        for (int v : adj[u]) if (!in_clique[v]) {
          cnt[v]--;
        }
      }
      for (int u : cl0) in_clique[u] = false;
    }
    q2.swap(q);
    sort_unique(q);
  }
  return ans;
}

vector<pair<int, int>> mark_graph(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<vector<bool>> A(n, vector<bool>(n, false));
  for (int u = 0; u < n; ++u) {
    for (int v : adj[u]) A[u][v] = true;
  }
  vector<array<int, 3>> triplets;
  for (int u = 0; u < n; ++u) {
    for (int v : adj[u]) {
      if (adj[v].size() <= adj[u].size()) {
        for (int w : adj[v]) {
          if (A[u][w]) {
            triplets.push_back({u, v, w});
          }
        }
      }
    }
  }
  sort_unique(triplets);
  vector<int> cnt(n, 0);
  vector<bool> in_cur(n, false);
  pair<int, vector<int>> best_set;
  best_set.first = -1;
  const int K = 5;
  for (const array<int, 3>& triplet : triplets) {
    vector<int> cur; cur.reserve(K);
    for (int i = 0; i < 3; ++i) {
      cur.push_back(triplet[i]);
      in_cur[cur[i]] = true;
    }
    while (int(cur.size()) < K) {
      pair<int, int> best{-1, -1};
      for (int u : cur) {
        for (int v : adj[u]) if (!in_cur[v]) {
          if (++cnt[v] > best.first) {
            best = {cnt[v], v};
          }
        }
      }
      if (best.first < 0) break;
      cur.push_back(best.second);
      in_cur[best.second] = true;
      for (int u : cur) {
        for (int v : adj[u]) if (!in_cur[v]) {
          cnt[v]--;
        }
      }
    }
    for (int u : cur) in_cur[u] = false;
    if (int(cur.size()) < K) continue;
    int n_edges = 0;
    for (int i = 0; i < int(cur.size()); ++i) {
      for (int j = 0; j < i; ++j) {
        n_edges += A[cur[i]][cur[j]];
      }
    }
    if (n_edges > best_set.first) {
      best_set = {n_edges, cur};
    }
  }
  vector<pair<int, int>> ans;
  for (int u : best_set.second) {
    for (int v : best_set.second) if ((v > u) && !A[u][v]) {
      ans.emplace_back(u, v);
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int max_clique1 = find_max_clique(adj);
  if (max_clique1 >= 5) {
    cout << "ok\n";
  }
  else {
    cout << "mark\n";
    vector<pair<int, int>> ans = mark_graph(adj);
    int k = ans.size();
    cout << k << '\n';
    for (auto [u, v] : ans) {
      cout << (u + 1) << ' ' << (v + 1) << '\n';
    }
  }
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 4ms

memory: 3888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 2ms

memory: 3936kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 6ms

memory: 3992kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 3ms

memory: 3948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 4ms

memory: 3920kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 3ms

memory: 3912kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 3ms

memory: 3888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 5ms

memory: 3960kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 6ms

memory: 3960kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 5ms

memory: 3912kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 4ms

memory: 3848kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 4ms

memory: 3952kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 2ms

memory: 3940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 3ms

memory: 3944kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 3ms

memory: 3844kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 3ms

memory: 3952kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 3ms

memory: 3944kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 6ms

memory: 3972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 5ms

memory: 3904kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 5ms

memory: 3984kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 4ms

memory: 3876kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 4ms

memory: 3892kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 4ms

memory: 3880kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 2ms

memory: 3876kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 4ms

memory: 3920kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 4ms

memory: 3904kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 3ms

memory: 3888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 4ms

memory: 4000kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 3ms

memory: 3876kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 4ms

memory: 3912kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 3ms

memory: 3880kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 4ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 6ms

memory: 4012kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 2ms

memory: 3896kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 2ms

memory: 3900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 2ms

memory: 3872kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 0ms

memory: 3900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 2ms

memory: 3940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 0ms

memory: 3836kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 2ms

memory: 3836kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 2ms

memory: 3884kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 2ms

memory: 3872kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 2ms

memory: 3932kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 2ms

memory: 3872kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 2ms

memory: 3940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 2ms

memory: 3900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 2ms

memory: 3948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 0ms

memory: 3864kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 6ms

memory: 3968kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 6ms

memory: 4080kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 6ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 6ms

memory: 4036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 6ms

memory: 4044kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 5ms

memory: 4024kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 6ms

memory: 4076kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 5ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 5ms

memory: 4016kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 6ms

memory: 3964kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 6ms

memory: 3980kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 6ms

memory: 4076kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 6ms

memory: 4024kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 6ms

memory: 4116kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 6ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right