Submission #403674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403674	2021-05-13T11:08:17 Z	errorgorn	None (KOI16_laser)	C++17	0 / 100	2000 ms	2332 KB

laser

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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());

const double EPS=1e-8;

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

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

double cost[425][425];
int cap[425][425];

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

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

double 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;
	
	while (true){
		SPFA(s,t);
		
		//cout<<w[t]<<endl;
		if (w[t]>1e12) break;
		
		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	2 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	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	2 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	2 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	2 ms	460 KB	Output is correct
21	Incorrect	2 ms	460 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	351 ms	1720 KB	Output is correct
2	Correct	231 ms	1356 KB	Output is correct
3	Correct	285 ms	1524 KB	Output is correct
4	Correct	143 ms	1744 KB	Output is correct
5	Correct	148 ms	1756 KB	Output is correct
6	Correct	201 ms	1996 KB	Output is correct
7	Correct	66 ms	1476 KB	Output is correct
8	Correct	315 ms	2304 KB	Output is correct
9	Correct	156 ms	1740 KB	Output is correct
10	Correct	228 ms	2188 KB	Output is correct
11	Correct	1872 ms	2328 KB	Output is correct
12	Correct	1772 ms	2332 KB	Output is correct
13	Execution timed out	2001 ms	2332 KB	Time limit exceeded
14	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	2 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	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	2 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	2 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	2 ms	460 KB	Output is correct
21	Incorrect	2 ms	460 KB	Output isn't correct
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	2 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	460 KB	Output is correct
15	Correct	1 ms	460 KB	Output is correct
16	Correct	2 ms	460 KB	Output is correct
17	Correct	1 ms	460 KB	Output is correct
18	Correct	2 ms	460 KB	Output is correct
19	Correct	1 ms	460 KB	Output is correct
20	Correct	2 ms	460 KB	Output is correct
21	Incorrect	2 ms	460 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #403674

Compilation message

Subtask #1 0 / 14.0

Subtask #2 0 / 19.0

Subtask #3 0 / 33.0

Subtask #4 0 / 34.0

Subtask #1
0 / 14.0

Subtask #2
0 / 19.0

Subtask #3
0 / 33.0

Subtask #4
0 / 34.0