QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#295998	#4829. Mark on a Graph	hos_lyric	AC ✓	2ms	4800kb	C++14	4.0kb	2024-01-01 21:31:10	2024-01-01 21:31:10

Judging History

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

[2024-01-01 21:31:10]
评测

测评结果：AC
用时：2ms
内存：4800kb

查看

[2024-01-01 21:31:10]
提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int N, M;
bool adj[1010][1010];

void gen(int seed) {
  mt19937_64 rng(seed);
  memset(adj, 0, sizeof(adj));
  for (int i = 0; i < M; ++i) {
    for (; ; ) {
      const int u = rng() % N;
      const int v = rng() % N;
      if (u != v && !adj[u][v]) {
        adj[u][v] = adj[v][u] = true;
        break;
      }
    }
  }
}

void expr() {
  int freq[6 + 1][15 + 1] = {};
  for (int seed = 0; seed < 10'000; ++seed) {
    gen(seed);
    vector<int> deg(N, 0);
    for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (adj[u][v]) {
      ++deg[u];
    }
    vector<int> us(N);
    for (int u = 0; u < N; ++u) us[u] = u;
    sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return ((deg[u] != deg[v]) ? (deg[u] > deg[v]) : (u < v));
    });
    /*
    for (int x = 0; x < 6; ++x) {
      printf("%2d ", deg[us[x]]);
      for (int y = 0; y < 6; ++y) {
        printf("%d", adj[us[x]][us[y]]);
      }
      puts("");
    }
    puts("");
    */
    for (int k = 0; k <= 6; ++k) {
      int cnt = 0;
      for (int x = 0; x < k; ++x) for (int y = x + 1; y < k; ++y) if (adj[us[x]][us[y]]) {
        ++cnt;
      }
      ++freq[k][cnt];
    }
  }
  for (int k = 0; k <= 6; ++k) {
    cerr << k << ": "; pv(freq[k], freq[k] + (k*(k-1)/2 + 1));
  }
}
/*
seed \in [0, 10^4)

M = 1500

0: 10000
1: 10000
2: 9672 328
3: 9125 849 26 0
4: 8425 1478 95 2 0 0 0
5: 7619 2136 228 17 0 0 0 0 0 0 0
6: 6726 2745 478 48 3 0 0 0 0 0 0 0 0 0 0 0

M = 5000

0: 10000
1: 10000
2: 9533 467
3: 8717 1229 53 1
4: 7669 2085 236 10 0 0 0
5: 6526 2894 526 51 3 0 0 0 0 0 0
6: 5364 3473 983 161 18 1 0 0 0 0 0 0 0 0 0 0
*/

int main() {
  /*
  N = 1000;
  M = 1500;
  expr();
  M = 5000;
  expr();
  */
  
  scanf("%d%d", &N, &M);
  memset(adj, 0, sizeof(adj));
  for (int i = 0; i < M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    adj[u][v] = adj[v][u] = true;
  }
  
  vector<int> deg(N, 0);
  for (int u = 0; u < N; ++u) for (int v = 0; v < N; ++v) if (adj[u][v]) {
    ++deg[u];
  }
  vector<int> us(N);
  for (int u = 0; u < N; ++u) us[u] = u;
  sort(us.begin(), us.end(), [&](int u, int v) -> bool {
    return ((deg[u] != deg[v]) ? (deg[u] > deg[v]) : (u < v));
  });
  int cnt = 0;
  for (int x = 0; x < 5; ++x) for (int y = x + 1; y < 5; ++y) if (adj[us[x]][us[y]]) {
    ++cnt;
  }
  if (cnt >= 5) {
    puts("ok");
  } else {
    vector<pair<int, int>> ans;
    for (int x = 0; x < 5; ++x) for (int y = x + 1; y < 5; ++y) if (!adj[us[x]][us[y]]) {
      ans.emplace_back(us[x], us[y]);
    }
    ans.resize(5);
    puts("mark");
    printf("%d\n", (int)ans.size());
    for (const auto &e : ans) {
      printf("%d %d\n", e.first + 1, e.second + 1);
    }
  }
  
  return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 2ms

memory: 4800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 2ms

memory: 4632kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 2ms

memory: 4624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 2ms

memory: 4692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 2ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 2ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 2ms

memory: 4736kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 2ms

memory: 4744kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 1ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 2ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 2ms

memory: 4792kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 2ms

memory: 4748kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 2ms

memory: 4796kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 2ms

memory: 4668kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 2ms

memory: 4800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 0ms

memory: 4684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 2ms

memory: 4676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 2ms

memory: 4620kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 2ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 2ms

memory: 4676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 2ms

memory: 4620kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 2ms

memory: 4764kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 2ms

memory: 4700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 2ms

memory: 4748kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 2ms

memory: 4680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 2ms

memory: 4692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 2ms

memory: 4680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 2ms

memory: 4680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 2ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 2ms

memory: 4684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 1ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 0ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 2ms

memory: 4700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 1ms

memory: 4684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 2ms

memory: 4692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 2ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 2ms

memory: 4676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 2ms

memory: 4624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 2ms

memory: 4680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 2ms

memory: 4744kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 2ms

memory: 4800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 0ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 2ms

memory: 4768kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 2ms

memory: 4680kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 2ms

memory: 4740kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 2ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 2ms

memory: 4676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 2ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 2ms

memory: 4700kb

input:

output:

input:

output:

ok

result:

ok all right