oj.uz

Submission #939139

# Submission time Handle Problem Language Result Execution time Memory
939139 2024-03-06T06:11:57 Z winter0101 City Mapping (NOI18_citymapping) C++14
78.21 / 100
 5 ms 8792 KB 
#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(10101994);
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){
shuffle(all(tmp),rng);
for (auto v:tmp)add[v]=0;
if (sz(tmp)<=1)return;
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 {
sort(all(xd[u]),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
vector<int>lft,rht;
lft.pb(xd[u][0]);
for (auto v:xd[u]){
if (v==xd[u][0])continue;
if (ask(xd[u][0],s)+ask(xd[u][0],v)==ask(s,v)){
lft.pb(v);
}
else {
rht.pb(v);
}
}
if (!lft.empty())add_edg(u,lft[0],ask(s,lft[0])-ask(s,u));
if (!rht.empty())add_edg(u,rht[0],ask(s,rht[0])-ask(s,u));
xd[u].clear();
solve(lft),solve(rht);
}
}
}
}
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 5 ms 8540 KB Correct: 8018 out of 500000 queries used.
2 Correct 3 ms 8540 KB Correct: 2514 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 8112 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 7393 out of 500000 queries used.
5 Correct 4 ms 8540 KB Correct: 7095 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Correct: 8018 out of 500000 queries used.
2 Correct 3 ms 8540 KB Correct: 2514 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 8112 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 7393 out of 500000 queries used.
5 Correct 4 ms 8540 KB Correct: 7095 out of 500000 queries used.
6 Correct 4 ms 8540 KB Correct: 6484 out of 500000 queries used.
7 Correct 3 ms 8588 KB Correct: 4962 out of 500000 queries used.
8 Correct 3 ms 8540 KB Correct: 7930 out of 500000 queries used.
9 Correct 3 ms 8540 KB Correct: 7222 out of 500000 queries used.
10 Correct 3 ms 8564 KB Correct: 7560 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Correct: 6582 out of 12000 queries used.
2 Correct 4 ms 8504 KB Correct: 6061 out of 12000 queries used.
3 Correct 4 ms 8540 KB Correct: 5956 out of 12000 queries used.
4 Correct 4 ms 8540 KB Correct: 4638 out of 12000 queries used.
5 Correct 3 ms 8540 KB Correct: 4403 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Correct: 6582 out of 12000 queries used.
2 Correct 4 ms 8504 KB Correct: 6061 out of 12000 queries used.
3 Correct 4 ms 8540 KB Correct: 5956 out of 12000 queries used.
4 Correct 4 ms 8540 KB Correct: 4638 out of 12000 queries used.
5 Correct 3 ms 8540 KB Correct: 4403 out of 12000 queries used.
6 Correct 4 ms 8536 KB Correct: 7331 out of 12000 queries used.
7 Correct 4 ms 8540 KB Correct: 6333 out of 12000 queries used.
8 Correct 4 ms 8536 KB Correct: 6861 out of 12000 queries used.
9 Correct 4 ms 8540 KB Correct: 8822 out of 12000 queries used.
10 Correct 4 ms 8540 KB Correct: 4891 out of 12000 queries used.

Subtask #5
21.21 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8540 KB Correct: 8018 out of 500000 queries used.
2 Correct 3 ms 8540 KB Correct: 2514 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 8112 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 7393 out of 500000 queries used.
5 Correct 4 ms 8540 KB Correct: 7095 out of 500000 queries used.
6 Correct 4 ms 8540 KB Correct: 6484 out of 500000 queries used.
7 Correct 3 ms 8588 KB Correct: 4962 out of 500000 queries used.
8 Correct 3 ms 8540 KB Correct: 7930 out of 500000 queries used.
9 Correct 3 ms 8540 KB Correct: 7222 out of 500000 queries used.
10 Correct 3 ms 8564 KB Correct: 7560 out of 500000 queries used.
11 Correct 4 ms 8540 KB Correct: 6582 out of 12000 queries used.
12 Correct 4 ms 8504 KB Correct: 6061 out of 12000 queries used.
13 Correct 4 ms 8540 KB Correct: 5956 out of 12000 queries used.
14 Correct 4 ms 8540 KB Correct: 4638 out of 12000 queries used.
15 Correct 3 ms 8540 KB Correct: 4403 out of 12000 queries used.
16 Correct 4 ms 8536 KB Correct: 7331 out of 12000 queries used.
17 Correct 4 ms 8540 KB Correct: 6333 out of 12000 queries used.
18 Correct 4 ms 8536 KB Correct: 6861 out of 12000 queries used.
19 Correct 4 ms 8540 KB Correct: 8822 out of 12000 queries used.
20 Correct 4 ms 8540 KB Correct: 4891 out of 12000 queries used.
21 Correct 4 ms 8536 KB Correct: 7252 out of 25000 queries used.
22 Correct 4 ms 8540 KB Correct: 3886 out of 25000 queries used.
23 Correct 3 ms 8540 KB Correct: 9598 out of 25000 queries used.
24 Correct 3 ms 8540 KB Correct: 6097 out of 25000 queries used.
25 Correct 3 ms 8540 KB Correct: 6799 out of 25000 queries used.
26 Correct 3 ms 8536 KB Correct: 6617 out of 25000 queries used.
27 Correct 3 ms 8540 KB Correct: 7607 out of 25000 queries used.
28 Correct 3 ms 8472 KB Correct: 6918 out of 25000 queries used.
29 Correct 3 ms 8540 KB Correct: 7325 out of 25000 queries used.
30 Correct 3 ms 8508 KB Correct: 6582 out of 25000 queries used.
31 Correct 3 ms 8540 KB Correct: 7514 out of 25000 queries used.
32 Correct 4 ms 8692 KB Correct: 3763 out of 25000 queries used.
33 Correct 3 ms 8564 KB Correct: 7766 out of 25000 queries used.
34 Correct 3 ms 8540 KB Correct: 7675 out of 25000 queries used.
35 Correct 3 ms 8540 KB Correct: 7314 out of 25000 queries used.
36 Correct 3 ms 8540 KB Correct: 7729 out of 25000 queries used.
37 Correct 3 ms 8792 KB Correct: 6991 out of 25000 queries used.
38 Correct 3 ms 8536 KB Correct: 9770 out of 25000 queries used.
39 Correct 3 ms 8540 KB Correct: 6989 out of 25000 queries used.
40 Correct 5 ms 8468 KB Correct: 8583 out of 25000 queries used.
41 Correct 3 ms 8540 KB Correct: 7099 out of 25000 queries used.
42 Correct 3 ms 8476 KB Correct: 8010 out of 25000 queries used.
43 Correct 3 ms 8464 KB Correct: 5254 out of 25000 queries used.
44 Correct 3 ms 8472 KB Correct: 9572 out of 25000 queries used.
45 Correct 3 ms 8540 KB Correct: 7823 out of 25000 queries used.
46 Correct 3 ms 8540 KB Correct: 7382 out of 25000 queries used.
47 Correct 4 ms 8540 KB Correct: 8743 out of 25000 queries used.
48 Correct 3 ms 8540 KB Correct: 7073 out of 25000 queries used.
49 Correct 3 ms 8536 KB Correct: 6957 out of 25000 queries used.
50 Correct 4 ms 8536 KB Correct: 9256 out of 25000 queries used.
51 Correct 3 ms 8540 KB Correct: 9945 out of 25000 queries used.
52 Correct 3 ms 8540 KB Correct: 7731 out of 25000 queries used.
53 Correct 3 ms 8524 KB Correct: 7372 out of 25000 queries used.
54 Correct 4 ms 8540 KB Correct: 8670 out of 25000 queries used.
55 Correct 3 ms 8540 KB Correct: 7620 out of 25000 queries used.
56 Correct 3 ms 8520 KB Correct: 7708 out of 25000 queries used.
57 Correct 3 ms 8472 KB Correct: 6856 out of 25000 queries used.
58 Correct 3 ms 8540 KB Correct: 9041 out of 25000 queries used.
59 Correct 3 ms 8540 KB Correct: 7468 out of 25000 queries used.
60 Correct 4 ms 8540 KB Correct: 7251 out of 25000 queries used.
61 Correct 3 ms 8540 KB Correct: 6884 out of 25000 queries used.
62 Correct 4 ms 8468 KB Correct: 5773 out of 25000 queries used.
63 Correct 4 ms 8540 KB Correct: 9624 out of 25000 queries used.
64 Correct 3 ms 8540 KB Correct: 6977 out of 25000 queries used.
65 Correct 3 ms 8536 KB Correct: 7059 out of 25000 queries used.
66 Correct 3 ms 8540 KB Correct: 6228 out of 25000 queries used.
67 Correct 3 ms 8540 KB Correct: 6140 out of 25000 queries used.
68 Correct 3 ms 8540 KB Correct: 4590 out of 25000 queries used.
69 Correct 4 ms 8540 KB Correct: 5632 out of 25000 queries used.
70 Correct 4 ms 8540 KB Correct: 9889 out of 25000 queries used.