QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#295627	#4829. Mark on a Graph	bachbeo2007	AC ✓	2ms	4928kb	C++23	3.6kb	2023-12-31 16:58:15	2023-12-31 16:58:15

Judging History

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

[2023-12-31 16:58:15]
评测

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

查看

[2023-12-31 16:58:15]
提交

answer

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

template<bool Enable_small_to_large = true>
struct disjoint_set{
	int n, _classes;
	vector<int> p;
	disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
	int make_set(){
		p.push_back(-1);
		++ _classes;
		return n ++;
	}
	int classes() const{
		return _classes;
	}
	int root(int u){
		return p[u] < 0 ? u : p[u] = root(p[u]);
	}
	bool share(int a, int b){
		return root(a) == root(b);
	}
	int size(int u){
		return -p[root(u)];
	}
	bool merge(int u, int v){
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _classes;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
		p[u] += p[v], p[v] = u;
		return true;
	}
	bool merge(int u, int v, auto act){
		u = root(u), v = root(v);
		if(u == v) return false;
		-- _classes;
		bool swapped = false;
		if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
		p[u] += p[v], p[v] = u;
		act(u, v, swapped);
		return true;
	}
	void clear(){
		_classes = n;
		fill(p.begin(), p.end(), -1);
	}
	vector<vector<int>> group_up(){
		vector<vector<int>> g(n);
		for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
		g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
		return g;
	}
};

const int N = 1e3 + 5, M = 5e3 + 5;

int n, m;
vector <int> adj[N];
bool madj[N][N];

void connect_edge(int u, int v){
	adj[u].emplace_back(v);
	adj[v].emplace_back(u);
	madj[u][v] = madj[v][u] = true;
}

bool f(){
	vector <pair <int, int>> a;
	ForE(u, 1, n){
		a.emplace_back(pair{isz(adj[u]), u});
	}
	sort(bend(a), greater<>());

	a.resize(5);
	if (a[3].first == a[4].first){
		return false;
	}
	int cnt = 0;
	For(i, 0, 4){
		For(j, i + 1, 4){
			int u = a[i].second, v = a[j].second;
			cnt += madj[u][v];
		}
	}
	return cnt >= 5;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// freopen("KEK.inp", "r", stdin);
	// freopen("KEK.out", "w", stdout);
	cin >> n >> m;
	ForE(i, 1, m){
		int u, v; cin >> u >> v;
		connect_edge(u, v);
	}

	if (f()){
		cout << "ok" << endl;
		return 0;
	}
	vector <pair <int, int>> a;
	ForE(u, 1, n){
		a.emplace_back(isz(adj[u]), u);
	}
	sort(bend(a), greater<>());
	vector <pair <int, int>> edges;
	For(i, 0, 4){
		For(j, i + 1, 4){
			if (isz(edges) == 5) continue;
			int u = a[i].second, v = a[j].second;
			if (not madj[u][v]){
				connect_edge(u, v);
				edges.emplace_back(u, v);
			}
		}
	}
	cout << "mark" << endl;
	cout << isz(edges) << endl;
	for (auto &[u, v]: edges){
		cout << u << ' ' << v << endl;
	}
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 4892kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 1ms

memory: 4644kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 1ms

memory: 4716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 1ms

memory: 4660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 1ms

memory: 4624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 1ms

memory: 4704kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 1ms

memory: 4888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 1ms

memory: 4664kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 2ms

memory: 4728kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 1ms

memory: 4864kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 1ms

memory: 4700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 1ms

memory: 4688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 1ms

memory: 4656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 1ms

memory: 4892kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 1ms

memory: 4672kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 1ms

memory: 4692kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 1ms

memory: 4656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 2ms

memory: 4612kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 1ms

memory: 4908kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 1ms

memory: 4908kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 1ms

memory: 4584kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 1ms

memory: 4884kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 1ms

memory: 4908kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 1ms

memory: 4696kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 2ms

memory: 4684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 1ms

memory: 4900kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 1ms

memory: 4916kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 1ms

memory: 4624kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 1ms

memory: 4648kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 1ms

memory: 4640kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 1ms

memory: 4860kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 1ms

memory: 4716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 1ms

memory: 4828kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 1ms

memory: 4664kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 1ms

memory: 4860kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 1ms

memory: 4860kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 1ms

memory: 4676kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 0ms

memory: 4828kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 1ms

memory: 4684kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 1ms

memory: 4640kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 1ms

memory: 4864kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 1ms

memory: 4604kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 1ms

memory: 4576kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 1ms

memory: 4656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 1ms

memory: 4656kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 1ms

memory: 4928kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 1ms

memory: 4908kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 1ms

memory: 4924kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 1ms

memory: 4716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 1ms

memory: 4724kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 1ms

memory: 4700kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 1ms

memory: 4924kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 1ms

memory: 4924kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 2ms

memory: 4612kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 1ms

memory: 4724kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 1ms

memory: 4652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 1ms

memory: 4876kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 1ms

memory: 4660kb

input:

output:

input:

output:

ok

result:

ok all right