oj.uz

Submission #852231

# Submission time Handle Problem Language Result Execution time Memory
852231 2023-09-21T13:06:27 Z Wansur Longest Trip (IOI23_longesttrip) C++17
0 / 100
 6 ms 856 KB 
#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;

const int mx=2e2+12;

vector<int> g[mx];
int was[mx][mx];

bool are_connected(std::vector<int> A, std::vector<int> B);

int  ask(int a,int b){
	if(!was[a][b]){
		was[a][b]=was[b][a]=(int)are_connected({a},{b})+1;
	}
	return was[a][b]-1;
}

std::vector<int> longest_trip(int n, int d){
	vector<int> ans;
	for(int i=0;i<n;i++){
		g[i].clear();
		for(int j=0;j<n;j++){
			was[i][j]=0;
		}
	}
	srand(time(0));
	vector<int> t;
	for(int i=0;i<n;i++){
		g[i].push_back(i);
		t.push_back(i);
	}
	while(t.size()>2){
		int a=t[0],b=t[1],c=t[2];
		vector<pair<int,int>> d;
		d.push_back({a,b});
		d.push_back({a,c});
		d.push_back({b,c});
		random_shuffle(d.begin(),d.end());
		int v,u;
		if(ask(d[0].f,d[0].s)){
			v=d[0].f,u=d[0].s;
		}
		else if(ask(d[1].f,d[1].s)){
			v=d[1].f,u=d[1].s;
		}
		else{
			v=d[2].f,u=d[2].s;
		}
		reverse(g[v].begin(),g[v].end());
		for(int x:g[u]){
			g[v].push_back(x);
		}
		g[u].clear();
		int x=g[v][0];
		if(x!=v){
			for(int to:g[v]){
				g[x].push_back(to);
			}
			g[v].clear();
		}
		t.clear();
		for(int i=0;i<n;i++){
			if((int)g[i].size()>0){
				t.push_back(i);
			}
		}
	}
	int a=t[0],b=t[1];
	if((int)g[a].size()>(int)g[b].size()){
		return g[a];
	}
	else{
		return g[b];
	}
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 716 KB Output is correct
5 Runtime error 1 ms 856 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -