oj.uz

Submission #403680

# Submission time Handle Problem Language Result Execution time Memory
403680 2021-05-13T11:10:53 Z errorgorn None (KOI16_laser) C++17
0 / 100
 2000 ms 3660 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

#define ld long double

const ld EPS=1e-10;

int n;
ii arr[1005];
ii brr[2005];

const int s=420,t=421;
const int BUF=105;

ld cost[425][425];
int cap[425][425];

ld sq(ld i){
	return i*i;
}

ld dist(int i,int j){
	return sqrtl(sq(arr[i].fi-brr[j].fi)+sq(arr[i].se-brr[j].se));
}

ld w[425];
int p[425];
bool inq[425];
queue<int> q;

void SPFA(int i,int j){
	rep(x,0,425) w[x]=2e12;
	w[i]=0;
	
	inq[i]=true,q.push(i);
	
	while (!q.empty()){
		int node=q.front();
		q.pop();
		inq[node]=false;
		
		rep(x,0,425) if (cap[node][x]>0 && w[x]-EPS>w[node]+cost[node][x]){
			w[x]=w[node]+cost[node][x];
			p[x]=node;
			
			if (!inq[x]){
				inq[x]=true,q.push(x);
			}
		}
	}
}

vector<int> ans[105];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se;
	rep(x,0,2*n) cin>>brr[x].fi>>brr[x].se;
	
	rep(x,0,n){
		rep(y,0,2*n){
			cost[x][y+2*BUF]=cost[x+BUF][y+2*BUF]=dist(x,y);
			cost[y+2*BUF][x]=cost[y+2*BUF][x+BUF]=-dist(x,y);
			
			cap[x][y+2*BUF]=cap[x+BUF][y+2*BUF]=1;
		}
	}
	
	rep(x,0,n) cap[s][x]=cap[s][x+BUF]=1;
	rep(y,0,2*n) cap[y+2*BUF][t]=1;
	
	rep(zzz,0,2*n){
		SPFA(s,t);
		
		vector<int> v={t};
		
		while (v.back()!=s){
			v.pub(p[v.back()]);
		}
		
		reverse(all(v));
		
		//the cap is definitely 1
		rep(x,0,sz(v)-1){
			//cout<<"debug: "<<v[x]<<" "<<v[x+1]<<endl;
			cap[v[x]][v[x+1]]--;
			cap[v[x+1]][v[x]]++;
		}
		//cout<<endl;
	}
	
	rep(x,0,n){
		rep(y,0,2*n){
			if (cap[x][y+2*BUF]==0) ans[x].pub(y);
			if (cap[x+BUF][y+2*BUF]==0) ans[x].pub(y);
		}
	}
	
	rep(x,0,n){
		cout<<ans[x][0]+1<<" "<<ans[x][1]+1<<endl;
	}
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 396 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Execution timed out 2090 ms 460 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 2552 KB Output is correct
2 Correct 270 ms 1944 KB Output is correct
3 Correct 317 ms 2204 KB Output is correct
4 Correct 160 ms 2508 KB Output is correct
5 Correct 169 ms 2636 KB Output is correct
6 Correct 235 ms 3172 KB Output is correct
7 Correct 74 ms 1868 KB Output is correct
8 Correct 369 ms 3604 KB Output is correct
9 Correct 172 ms 2592 KB Output is correct
10 Correct 263 ms 3404 KB Output is correct
11 Execution timed out 2087 ms 3660 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 396 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Execution timed out 2090 ms 460 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 2 ms 396 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Execution timed out 2090 ms 460 KB Time limit exceeded
22 Halted 0 ms 0 KB -