QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98732#4218. Hidden Graph_yjhWA 4ms3560kbC++141.8kb2023-04-19 21:30:482023-04-19 21:30:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-19 21:30:51]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3560kb
  • [2023-04-19 21:30:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int n,mx,m,col[2005],d[2005];
bool del[2005],vis[2005];
vector <int> nt[2005];
vector <int> v[2005];
queue <int> q;
int main() {
	cin>>n;
	nt[1].push_back(1);
	mx=1;
	for(int nw=2;nw<=n;nw++) {
		for(int i=1;i<=mx;i++) {
			if(!nt[i].size()) continue;
			int sz=nt[i].size();
			while(sz) {
				cout<<"? "<<sz+1<<' ';
				for(int k:nt[i]) {
					if(!del[k]) cout<<k<<' ';
				}
				cout<<nw<<endl;
				int x,y;
				cin>>x>>y;
				if(x==-1||y==-1) break;
				if(x==nw) swap(x,y);
				v[y].push_back(x);
				v[x].push_back(y);
				m++;
				del[x]=true;
				sz--;
			}
			nt[i].clear();
		}
		mx=n+1;
		for(int i=1;i<=nw;i++) {
			del[i]=false;
			col[i]=0;
//			cout<<i<<' '<<v[i].size()<<'\n';
			mx=min(mx,int(v[i].size())+1);
		    d[i]=v[i].size();
		}
//		cout<<mx<<'\n';
//		if(n==2000) assert(mx<=3);
		for(int i=1;i<=nw;i++) {
			if(d[i]<=mx-1) {
				q.push(i);
				break;
			}
		}
//		cout<<q.front()<<'\n';
		vector <int> tmp;
		while(!q.empty()) {
			int s=q.front();
			q.pop();
			tmp.clear();
			del[s]=true;
		    if(!col[s]) {
		    	for(int to:v[s]) {
		    		if(col[to]) tmp.push_back(col[to]);
				}
				sort(tmp.begin(),tmp.end());
				int nww=1;
				for(int i:tmp) {
					if(nww!=i) break;
					nww++;
				}
//				cout<<"S"<<nww<<'\n';
				col[s]=nww;
				for(int to:v[s]) {
					d[to]--;
					if(!del[to]) q.push(to); 
//					if(d[to]<=mx-1&&!del[to]) q.push(to);
				}
				nt[col[s]].push_back(s);
			}
		}
		for(int i=1;i<=nw;i++) {
			del[i]=false;
//			assert(col[i]);
//			cout<<col[i]<<' ';
		}
//		cout<<'\n';
	}
	cout<<'!'<<' '<<m<<'\n';
	for(int i=1;i<=n;i++) {
		for(int j:v[i]) {
			if(j<i) continue;
			cout<<i<<' '<<j<<'\n';
		}
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3528kb

input:

3
1 2
1 3
2 3

output:

? 2 1 2
? 2 1 3
? 2 2 3
! 3
1 2
1 3
2 3

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

10
1 2
1 3
-1 -1
-1 -1
1 4
4 5
2 5
-1 -1
-1 -1
2 6
-1 -1
-1 -1
3 7
-1 -1
-1 -1
-1 -1
4 8
3 8
-1 -1
-1 -1
3 9
-1 -1
-1 -1
4 10
3 10
-1 -1

output:

? 2 1 2
? 2 1 3
? 2 2 3
? 3 2 3 4
? 2 1 4
? 4 2 3 4 5
? 3 2 3 5
? 2 3 5
? 2 1 5
? 4 3 2 4 6
? 3 3 4 6
? 3 1 5 6
? 4 3 2 4 7
? 3 2 4 7
? 4 1 5 6 7
? 5 6 1 5 7 8
? 4 2 3 4 8
? 3 2 3 8
? 2 2 8
? 6 6 1 5 7 8 9
? 4 2 3 4 9
? 3 2 4 9
? 7 6 1 5 7 8 9 10
? 4 2 3 4 10
? 3 2 3 10
? 2 2 10
! 12
1 2
1 3
1 4
2 5...

result:

ok correct

Test #3:

score: 0
Accepted
time: 3ms
memory: 3484kb

input:

5
2 1
3 1
3 2
4 1
4 2
-1 -1
-1 -1
5 1
5 2

output:

? 2 1 2
? 2 1 3
? 2 2 3
? 2 1 4
? 2 2 4
? 2 3 4
? 3 3 4 5
? 2 1 5
? 2 2 5
! 7
1 2
1 3
1 4
1 5
2 3
2 4
2 5

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

3
2 1
1 3
-1 -1

output:

? 2 1 2
? 2 1 3
? 2 2 3
! 2
1 2
1 3

result:

ok correct

Test #5:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

6
1 2
3 1
3 2
-1 -1
4 2
3 4
4 5
-1 -1
2 5
3 5
-1 -1
-1 -1
3 6

output:

? 2 1 2
? 2 1 3
? 2 2 3
? 2 1 4
? 2 2 4
? 2 3 4
? 3 1 4 5
? 2 1 5
? 2 2 5
? 2 3 5
? 3 1 4 6
? 2 2 6
? 2 3 6
! 9
1 2
1 3
2 3
2 4
2 5
3 4
3 5
3 6
4 5

result:

ok correct

Test #6:

score: -100
Wrong Answer
time: 4ms
memory: 3560kb

input:

27
-1 -1
3 1
-1 -1
2 5
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
4 11
-1 -1
6 13
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
7 22
-1 -1
24 8
-1 -1
-1 -1
-1 -1

output:

? 2 1 2
? 2 1 3
? 2 2 4
? 2 2 5
? 2 4 6
? 2 4 7
? 2 4 8
? 2 4 9
? 2 4 10
? 2 4 11
? 2 6 12
? 2 6 13
? 2 7 14
? 2 7 15
? 2 7 16
? 2 7 17
? 2 7 18
? 2 7 19
? 2 7 20
? 2 7 21
? 2 7 22
? 2 8 23
? 2 8 24
? 2 9 25
? 2 9 26
? 2 9 27
! 6
1 3
2 5
4 11
6 13
7 22
8 24

result:

wrong answer read 6 edges but expected 88 edges