QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #209390 | #7107. Chaleur | Leasier | Compile Error | / | / | C++98 | 3.4kb | 2023-10-10 14:49:29 | 2023-10-10 14:49:30 |
Judging History
answer
#include <stdio.h>
#include <vector>
using namespace std;
typedef struct {
int nxt;
int end;
} Edge;
int cnt;
int head[100007], deg[100007], root[100007], sz[100007];
bool mark[100007], mark2[100007];
Edge edge[200007];
inline void init(int n){
cnt = 0;
for (int i = 1; i <= n; i++){
head[i] = deg[i] = 0;
root[i] = i;
sz[i] = 1;
mark[i] = mark2[i] = false;
}
}
inline void add_edge(int start, int end){
cnt++;
edge[cnt].nxt = head[start];
head[start] = cnt;
edge[cnt].end = end;
}
int get_root(int x){
if (root[x] == x) return x;
return root[x] = get_root(root[x]);
}
inline void merge(int x, int y){
int x_root = get_root(x), y_root = get_root(y);
if (x_root != y_root){
root[x_root] = y_root;
sz[y_root] += sz[x_root];
}
}
inline void update(int p, int q, int &x, int &y){
if (x < p){
x = p;
y = q;
} else if (x == p){
y += q;
}
}
int main(){
int t;
scanf("%d", &t);
for (int i = 1; i <= t; i++){
int n, m;
scanf("%d %d", &n, &m);
if (m == 0){
printf("%d 1\n", n);
continue;
}
int ncon = 0;
init(n);
for (int j = 1; j <= m; j++){
int a, b;
scanf("%d %d", &a, &b);
deg[a]++;
deg[b]++;
add_edge(a, b);
add_edge(b, a);
merge(a, b);
}
vector<int> tuan, must, candiate;
for (int j = 1; j <= n; j++){
int csz = sz[get_root(j)];
if (csz == 1){
ncon++;
} else {
tuan.push_back(j);
}
}
int mxv = 0, cnt;
while (1ll * mxv * (mxv + 1) / 2 <= m) mxv++;
for (int j = mxv; j >= 2; j--){
vector<int> _must, _candiate;
for (int k : tuan){
mark[k] = false;
if (deg[k] == j - 1){
for (int l = head[k]; l != 0; l = edge[l].nxt){
mark[edge[l].end] = true;
}
} else if (deg[k] >= j){
mark[k] = true;
}
}
for (int k : tuan){
if (deg[k] >= j - 1){
if (mark[k]){
_must.push_back(k);
} else {
_candiate.push_back(k);
}
}
}
if (_candiate.size() == 1){
_must.push_back(_candiate[0]);
_candiate.pop_back();
}
if (_must.size() > j || _must.size() + _candiate.size() < j) continue;
cnt = j;
must = _must;
candiate = _candiate;
break;
}
int cnt1 = -1, ans1, cnt2 = -1, ans2;
for (int j : tuan){
mark[j] = mark2[j] = false;
}
if (must.size() == cnt){
for (int j : must){
mark[j] = true;
}
update(cnt, 1, cnt1, ans1);
for (int k : must){
for (int l = head[k]; l != 0; l = edge[l].nxt){
if (!mark[edge[l].end]) update(2, 1, cnt1, ans1);
}
}
update(n - cnt, 1, cnt2, ans2);
for (int k : must){
int tot = n - cnt + 1;
for (int l = head[k]; l != 0; l = edge[l].nxt){
if (!mark[edge[l].end]) tot--;
}
update(tot, 1, cnt2, ans2);
}
} else {
for (int j : must){
mark[j] = true;
}
for (int j : candiate){
mark2[j] = true;
}
update(cnt, candiate.size(), cnt1, ans1);
for (int k : must){
for (int l = head[k]; l != 0; l = edge[l].nxt){
int x = edge[l].end;
if (!mark[x] && !mark2[x]) update(2, 1, cnt1, ans1);
}
}
update(n - must.size(), 1, cnt2, ans2);
for (int k : must){
int tot = n - cnt + 1;
for (int l = head[k]; l != 0; l = edge[l].nxt){
if (!mark[edge[l].end]) tot--;
}
update(tot, 1, cnt2, ans2);
}
}
printf("%d %d\n", ans1, ans2);
}
return 0;
}
Details
answer.code: In function ‘int main()’:
answer.code:90:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
90 | for (int k : tuan){
| ^~~~
answer.code:90:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:100:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
100 | for (int k : tuan){
| ^~~~
answer.code:100:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:120:30: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
120 | for (int j : tuan){
| ^~~~
answer.code:120:30: error: forming reference to reference type ‘std::vector<int>&’
answer.code:124:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
124 | for (int j : must){
| ^~~~
answer.code:124:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:128:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
128 | for (int k : must){
| ^~~~
answer.code:128:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:134:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
134 | for (int k : must){
| ^~~~
answer.code:134:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:142:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
142 | for (int j : must){
| ^~~~
answer.code:142:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:145:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
145 | for (int j : candiate){
| ^~~~~~~~
answer.code:145:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:149:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
149 | for (int k : must){
| ^~~~
answer.code:149:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:156:38: warning: range-based ‘for’ loops only available with ‘-std=c++11’ or ‘-std=gnu++11’
156 | for (int k : must){
| ^~~~
answer.code:156:38: error: forming reference to reference type ‘std::vector<int>&’
answer.code:58:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
58 | scanf("%d", &t);
| ~~~~~^~~~~~~~~~
answer.code:61:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
61 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
answer.code:70:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
70 | scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~