Submission #939174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
939174	2024-03-06T06:29:17 Z	winter0101	City Mapping (NOI18_citymapping)	C++14	81.51 / 100	5 ms	8792 KB

citymapping

#include<bits/stdc++.h>
#include "citymapping.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
vector<pii>aaa[1009];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long d[1009][1009];
long long ask(int x,int y){
if (d[x][y]!=-1)return d[x][y];
return d[x][y]=d[y][x]=get_distance(x,y);
}
bool add[1009];
vector<int>xd[1009];
void solve(vector<int>&tmp){
if (sz(tmp)<=1)return;
shuffle(all(tmp),rng);
for (auto v:tmp)add[v]=0;
shuffle(all(tmp),rng);
int s=tmp[0],t=tmp.back();
ask(s,t);
vector<int>vertice;
for (auto v:tmp){
if (ask(s,v)+ask(t,v)==ask(s,t)){
vertice.pb(v);
add[v]=1;
}
}
//cout<<s<<" "<<t<<'\n';
sort(all(vertice),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
auto add_edg=[&](int u,int v,int w){
aaa[u].pb({v,w});
aaa[v].pb({u,w});
//cerr<<u<<" "<<v<<" "<<w<<'\n';
return;
};
for1(i,1,sz(vertice)-1){
add_edg(vertice[i],vertice[i-1],ask(vertice[i],s)-ask(vertice[i-1],s));
}
for(auto v:tmp){
if (add[v])continue;
for (auto u:vertice){
if (ask(s,v)-ask(s,u)==ask(t,v)-ask(t,u)&&ask(s,v)>ask(s,u)){
xd[u].pb(v);
//cerr<<u<<" "<<v<<'\n';
}
}
}
for (auto u:vertice){
if (!xd[u].empty()){
if ((u!=s&&u!=t)||sz(aaa[u])>=2){
vector<int>cop;
cop.swap(xd[u]);
int mn=cop[0];
for (auto v:cop){
if (ask(s,v)<ask(s,mn)){
mn=v;
}
}
add_edg(u,mn,ask(s,mn)-ask(s,u));
solve(cop);
}
else {
vector<int>cop;
cop.swap(xd[u]);
cop.pb(u);
solve(cop);
}
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	for1(i,1,N){
	for1(j,1,N){
	d[i][j]=-1;
	}
	d[i][i]=0;
	}
	vector<int>tree;
	for1(i,1,N)tree.pb(i);
	solve(tree);
	int cnt=0;
	for1(i,1,N){
	for (auto v:aaa[i]){
    if (v.fi>i){
    A[cnt]=v.fi,B[cnt]=i,W[cnt]=v.se;
    cnt++;
    }
	}
	}
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Correct: 3704 out of 500000 queries used.
2	Correct	3 ms	8540 KB	Correct: 6929 out of 500000 queries used.
3	Correct	3 ms	8540 KB	Correct: 7182 out of 500000 queries used.
4	Correct	3 ms	8540 KB	Correct: 6906 out of 500000 queries used.
5	Correct	3 ms	8536 KB	Correct: 6292 out of 500000 queries used.

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Correct: 3704 out of 500000 queries used.
2	Correct	3 ms	8540 KB	Correct: 6929 out of 500000 queries used.
3	Correct	3 ms	8540 KB	Correct: 7182 out of 500000 queries used.
4	Correct	3 ms	8540 KB	Correct: 6906 out of 500000 queries used.
5	Correct	3 ms	8536 KB	Correct: 6292 out of 500000 queries used.
6	Correct	3 ms	8540 KB	Correct: 4234 out of 500000 queries used.
7	Correct	4 ms	8540 KB	Correct: 5123 out of 500000 queries used.
8	Correct	3 ms	8540 KB	Correct: 7662 out of 500000 queries used.
9	Correct	3 ms	8536 KB	Correct: 7641 out of 500000 queries used.
10	Correct	4 ms	8540 KB	Correct: 5341 out of 500000 queries used.

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Correct: 3271 out of 12000 queries used.
2	Correct	4 ms	8540 KB	Correct: 5991 out of 12000 queries used.
3	Correct	4 ms	8540 KB	Correct: 5604 out of 12000 queries used.
4	Correct	3 ms	8536 KB	Correct: 4621 out of 12000 queries used.
5	Correct	3 ms	8540 KB	Correct: 4532 out of 12000 queries used.

Subtask #4

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Correct: 3271 out of 12000 queries used.
2	Correct	4 ms	8540 KB	Correct: 5991 out of 12000 queries used.
3	Correct	4 ms	8540 KB	Correct: 5604 out of 12000 queries used.
4	Correct	3 ms	8536 KB	Correct: 4621 out of 12000 queries used.
5	Correct	3 ms	8540 KB	Correct: 4532 out of 12000 queries used.
6	Correct	4 ms	8540 KB	Correct: 4010 out of 12000 queries used.
7	Correct	3 ms	8540 KB	Correct: 4050 out of 12000 queries used.
8	Correct	5 ms	8540 KB	Correct: 4912 out of 12000 queries used.
9	Correct	4 ms	8444 KB	Correct: 5719 out of 12000 queries used.
10	Correct	4 ms	8540 KB	Correct: 6895 out of 12000 queries used.

Subtask #5

24.51 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Correct: 3704 out of 500000 queries used.
2	Correct	3 ms	8540 KB	Correct: 6929 out of 500000 queries used.
3	Correct	3 ms	8540 KB	Correct: 7182 out of 500000 queries used.
4	Correct	3 ms	8540 KB	Correct: 6906 out of 500000 queries used.
5	Correct	3 ms	8536 KB	Correct: 6292 out of 500000 queries used.
6	Correct	3 ms	8540 KB	Correct: 4234 out of 500000 queries used.
7	Correct	4 ms	8540 KB	Correct: 5123 out of 500000 queries used.
8	Correct	3 ms	8540 KB	Correct: 7662 out of 500000 queries used.
9	Correct	3 ms	8536 KB	Correct: 7641 out of 500000 queries used.
10	Correct	4 ms	8540 KB	Correct: 5341 out of 500000 queries used.
11	Correct	3 ms	8540 KB	Correct: 3271 out of 12000 queries used.
12	Correct	4 ms	8540 KB	Correct: 5991 out of 12000 queries used.
13	Correct	4 ms	8540 KB	Correct: 5604 out of 12000 queries used.
14	Correct	3 ms	8536 KB	Correct: 4621 out of 12000 queries used.
15	Correct	3 ms	8540 KB	Correct: 4532 out of 12000 queries used.
16	Correct	4 ms	8540 KB	Correct: 4010 out of 12000 queries used.
17	Correct	3 ms	8540 KB	Correct: 4050 out of 12000 queries used.
18	Correct	5 ms	8540 KB	Correct: 4912 out of 12000 queries used.
19	Correct	4 ms	8444 KB	Correct: 5719 out of 12000 queries used.
20	Correct	4 ms	8540 KB	Correct: 6895 out of 12000 queries used.
21	Correct	3 ms	8540 KB	Correct: 5158 out of 25000 queries used.
22	Correct	4 ms	8540 KB	Correct: 4217 out of 25000 queries used.
23	Correct	3 ms	8540 KB	Correct: 6328 out of 25000 queries used.
24	Correct	4 ms	8792 KB	Correct: 4738 out of 25000 queries used.
25	Correct	3 ms	8540 KB	Correct: 8005 out of 25000 queries used.
26	Correct	3 ms	8452 KB	Correct: 6649 out of 25000 queries used.
27	Correct	3 ms	8540 KB	Correct: 9339 out of 25000 queries used.
28	Correct	3 ms	8536 KB	Correct: 6922 out of 25000 queries used.
29	Correct	3 ms	8536 KB	Correct: 6708 out of 25000 queries used.
30	Correct	4 ms	8284 KB	Correct: 7552 out of 25000 queries used.
31	Correct	3 ms	8540 KB	Correct: 8301 out of 25000 queries used.
32	Correct	3 ms	8492 KB	Correct: 4572 out of 25000 queries used.
33	Correct	3 ms	8540 KB	Correct: 6944 out of 25000 queries used.
34	Correct	3 ms	8536 KB	Correct: 7078 out of 25000 queries used.
35	Correct	3 ms	8540 KB	Correct: 8687 out of 25000 queries used.
36	Correct	3 ms	8536 KB	Correct: 7499 out of 25000 queries used.
37	Correct	4 ms	8540 KB	Correct: 7248 out of 25000 queries used.
38	Correct	3 ms	8540 KB	Correct: 7434 out of 25000 queries used.
39	Correct	3 ms	8540 KB	Correct: 7105 out of 25000 queries used.
40	Correct	3 ms	8492 KB	Correct: 6758 out of 25000 queries used.
41	Correct	3 ms	8540 KB	Correct: 7165 out of 25000 queries used.
42	Correct	3 ms	8540 KB	Correct: 7226 out of 25000 queries used.
43	Correct	3 ms	8540 KB	Correct: 5753 out of 25000 queries used.
44	Correct	3 ms	8284 KB	Correct: 9284 out of 25000 queries used.
45	Correct	3 ms	8284 KB	Correct: 6927 out of 25000 queries used.
46	Correct	3 ms	8284 KB	Correct: 7713 out of 25000 queries used.
47	Correct	3 ms	8592 KB	Correct: 7626 out of 25000 queries used.
48	Correct	3 ms	8540 KB	Correct: 8976 out of 25000 queries used.
49	Correct	3 ms	8540 KB	Correct: 7669 out of 25000 queries used.
50	Correct	3 ms	8792 KB	Correct: 7229 out of 25000 queries used.
51	Correct	3 ms	8540 KB	Correct: 7719 out of 25000 queries used.
52	Correct	3 ms	8540 KB	Correct: 7957 out of 25000 queries used.
53	Correct	4 ms	8540 KB	Correct: 8727 out of 25000 queries used.
54	Correct	4 ms	8536 KB	Correct: 5270 out of 25000 queries used.
55	Correct	3 ms	8540 KB	Correct: 7411 out of 25000 queries used.
56	Correct	3 ms	8540 KB	Correct: 7478 out of 25000 queries used.
57	Correct	3 ms	8536 KB	Correct: 7997 out of 25000 queries used.
58	Correct	3 ms	8540 KB	Correct: 7451 out of 25000 queries used.
59	Correct	3 ms	8540 KB	Correct: 7163 out of 25000 queries used.
60	Correct	3 ms	8540 KB	Correct: 5479 out of 25000 queries used.
61	Correct	3 ms	8536 KB	Correct: 6979 out of 25000 queries used.
62	Correct	4 ms	8284 KB	Correct: 9018 out of 25000 queries used.
63	Correct	3 ms	8544 KB	Correct: 6102 out of 25000 queries used.
64	Correct	3 ms	8540 KB	Correct: 8107 out of 25000 queries used.
65	Correct	5 ms	8492 KB	Correct: 5328 out of 25000 queries used.
66	Correct	3 ms	8540 KB	Correct: 5828 out of 25000 queries used.
67	Correct	4 ms	8560 KB	Correct: 7608 out of 25000 queries used.
68	Correct	3 ms	8540 KB	Correct: 7451 out of 25000 queries used.
69	Correct	3 ms	8536 KB	Correct: 4436 out of 25000 queries used.
70	Correct	3 ms	8540 KB	Correct: 5911 out of 25000 queries used.