oj.uz

답안 #966043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966043 2024-04-19T09:53:54 Z Darren0724 즐거운 행로 (APIO20_fun) C++17
0 / 100
 3 ms 4564 KB 
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int N=100005;
int cntid=0;
const int INF=1e9;
vector<int> sz(N,1),pa(N),ans,dis(N);
priority_queue<pair<int,int>> pq[3];
vector<int> createFunTour(int n, int q) {
	int c1=n-1;
	int need=n/2+1;
	int mn=INF;
	for(int i=1;i<n;i++){
		int t=attractionsBehind(n-1, i);
		if(t>=need&&t<mn){
			mn=t;
			c1=i;
		}
	}
	vector<int> r;

	vector<int> dis0(N,0);
	for(int i=0;i<n;i++){
		dis0[i]=hoursRequired(c1,i);
		if(dis0[i]==1){
			r.push_back(i);
		}
	}
	int rsz=r.size()-1;
	assert(rsz<=2);
	vector<vector<int>> dis(rsz,vector<int>(N));
	vector<int> vis(N);
	for(int i=0;i<rsz;i++){
		for(int j=0;j<n;j++){
			dis[i][j]=hoursRequired(r[i],j);
		}
	}
	for(int i=0;i<n;i++){
		if(i==c1)continue;
		int p=-1;
		for(int j=0;j<rsz;j++){
			if(dis[j][i]<dis0[i]){
				p=j;break;
			}
		}
		if(p==-1)p=rsz;
		pq[p].push({dis0[i],i});
	}
	cntid=r.size();
	int last=-1;
	for(int i=1;i<n;i++){
		array<int,3> p={-1,-1,-1};
		for(int j=0;j<cntid;j++){
			if(j==last||pq[j].size()==0)continue;
			p=max(p,array<int,3>{pq[j].top().first,(int)pq[j].size(),j});
		}
		last=p[2];
		assert(last!=-1&&pq[last].size()>0);
		auto [dis1,idx]=pq[last].top();
		pq[last].pop();
		ans.push_back(idx);
	}
	ans.push_back(c1);
	/*for(int j:ans){
		cout<<j<<' ';
	}
	cout<<endl;*/
  	return ans;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 3 ms 4564 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 3 ms 4564 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 3 ms 4564 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Runtime error 3 ms 4564 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Runtime error 3 ms 4564 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -