oj.uz

답안 #939350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939350 2024-03-06T09:39:29 Z winter0101 City Mapping (NOI18_citymapping) C++14
57.1 / 100
 7 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(101094);
vector<int>cc[1009];
int f[1009];
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);
}
int fs(int u){
if (f[u]<0)return u;
return f[u]=fs(f[u]);
}
void unite(int u,int v,int w){
int u1=u,v1=v;
u=fs(u),v=fs(v);
if (u==v)return;
if (f[u]>f[v]){
swap(u,v);
swap(u1,v1);
}
f[u]+=f[v];
for (auto vx:cc[u]){
for (auto vy:cc[v]){
d[vx][vy]=d[vy][vx]=1ll*w+d[vx][u1]+d[vy][v1];
}
}
for (auto vx:cc[v]){
cc[u].pb(vx);
}
cc[v].clear();
}
bool add[1009];
vector<int>xd[1009];
void solve(vector<int>&tmp,int s,int t){
if (sz(tmp)<=1)return;
for (auto v:tmp)add[v]=0;
sort(all(tmp),[&](int i,int j){
return ask(s,i)<ask(s,j);
});
t=tmp.back();
sort(all(tmp),[&](int i,int j){
return ask(t,i)<ask(t,j);
});
if (ask(s,t)<ask(t,tmp.back()))s=tmp.back();
vector<int>vertice;
for (auto v:tmp){
if (ask(s,v)+ask(t,v)==ask(s,t)){
vertice.pb(v);
add[v]=1;
}
}
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});
d[u][v]=d[v][u]=w;
unite(u,v,w);
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);
}
}
}
for (auto u:vertice){
if (!xd[u].empty()){
sort(all(xd[u]),[&](int i,int j){
return ask(i,s)<ask(j,s);
});
for (auto v:xd[u]){
d[u][v]=d[v][u]=ask(v,s)-ask(u,s);
}
if (u!=s&&u!=t){
int news=xd[u][0],newt=xd[u].back();
add_edg(u,xd[u][0],d[u][xd[u][0]]);
for (auto v:xd[u]){
d[v][xd[u][0]]=d[xd[u][0]][v]=d[u][v]-d[u][xd[u][0]];
}
vector<int>cop;
cop.swap(xd[u]);
solve(cop,newt,news);
}
else {
vector<int>cop;
int news=u,newt=xd[u].back();
cop.swap(xd[u]);
cop.pb(u);
solve(cop,newt,news);
}
}
}
}
void find_roads(int N, int Q, int A[], int B[], int W[]) {
	for1(i,1,N){
    f[i]=-1;
    cc[i].pb(i);
	for1(j,1,N){
	d[i][j]=-1;
	}
	d[i][i]=0;
	}
	vector<int>tree;
	for1(i,1,N)tree.pb(i);
	int s=rng()%N+1,t;
	while (true){
    t=rng()%N+1;
    if (s==t)continue;
    break;
	}
	solve(tree,s,t);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8540 KB Correct: 2991 out of 500000 queries used.
2 Correct 4 ms 8540 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 5972 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 6623 out of 500000 queries used.
5 Correct 5 ms 8540 KB Correct: 11971 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8540 KB Correct: 2991 out of 500000 queries used.
2 Correct 4 ms 8540 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 5972 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 6623 out of 500000 queries used.
5 Correct 5 ms 8540 KB Correct: 11971 out of 500000 queries used.
6 Correct 3 ms 8536 KB Correct: 2982 out of 500000 queries used.
7 Correct 7 ms 8540 KB Correct: 20413 out of 500000 queries used.
8 Correct 4 ms 8540 KB Correct: 5991 out of 500000 queries used.
9 Correct 3 ms 8540 KB Correct: 6992 out of 500000 queries used.
10 Correct 4 ms 8596 KB Correct: 7104 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Correct: 2967 out of 12000 queries used.
2 Correct 3 ms 8540 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 8540 KB Correct: 2994 out of 12000 queries used.
4 Correct 3 ms 8600 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 8540 KB Correct: 2967 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Correct: 2967 out of 12000 queries used.
2 Correct 3 ms 8540 KB Correct: 2973 out of 12000 queries used.
3 Correct 3 ms 8540 KB Correct: 2994 out of 12000 queries used.
4 Correct 3 ms 8600 KB Correct: 2973 out of 12000 queries used.
5 Correct 3 ms 8540 KB Correct: 2967 out of 12000 queries used.
6 Correct 3 ms 8540 KB Correct: 2988 out of 12000 queries used.
7 Correct 3 ms 8540 KB Correct: 2982 out of 12000 queries used.
8 Correct 3 ms 8536 KB Correct: 2994 out of 12000 queries used.
9 Correct 3 ms 8520 KB Correct: 2985 out of 12000 queries used.
10 Correct 3 ms 8696 KB Correct: 2976 out of 12000 queries used.

Subtask #5
0.1 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 8540 KB Correct: 2991 out of 500000 queries used.
2 Correct 4 ms 8540 KB Correct: 2994 out of 500000 queries used.
3 Correct 3 ms 8540 KB Correct: 5972 out of 500000 queries used.
4 Correct 3 ms 8540 KB Correct: 6623 out of 500000 queries used.
5 Correct 5 ms 8540 KB Correct: 11971 out of 500000 queries used.
6 Correct 3 ms 8536 KB Correct: 2982 out of 500000 queries used.
7 Correct 7 ms 8540 KB Correct: 20413 out of 500000 queries used.
8 Correct 4 ms 8540 KB Correct: 5991 out of 500000 queries used.
9 Correct 3 ms 8540 KB Correct: 6992 out of 500000 queries used.
10 Correct 4 ms 8596 KB Correct: 7104 out of 500000 queries used.
11 Correct 3 ms 8536 KB Correct: 2967 out of 12000 queries used.
12 Correct 3 ms 8540 KB Correct: 2973 out of 12000 queries used.
13 Correct 3 ms 8540 KB Correct: 2994 out of 12000 queries used.
14 Correct 3 ms 8600 KB Correct: 2973 out of 12000 queries used.
15 Correct 3 ms 8540 KB Correct: 2967 out of 12000 queries used.
16 Correct 3 ms 8540 KB Correct: 2988 out of 12000 queries used.
17 Correct 3 ms 8540 KB Correct: 2982 out of 12000 queries used.
18 Correct 3 ms 8536 KB Correct: 2994 out of 12000 queries used.
19 Correct 3 ms 8520 KB Correct: 2985 out of 12000 queries used.
20 Correct 3 ms 8696 KB Correct: 2976 out of 12000 queries used.
21 Correct 3 ms 8540 KB Correct: 2982 out of 25000 queries used.
22 Correct 4 ms 8524 KB Correct: 6208 out of 25000 queries used.
23 Correct 4 ms 8540 KB Correct: 3034 out of 25000 queries used.
24 Correct 4 ms 8540 KB Correct: 4400 out of 25000 queries used.
25 Correct 4 ms 8584 KB Correct: 6023 out of 25000 queries used.
26 Correct 4 ms 8536 KB Correct: 5791 out of 25000 queries used.
27 Correct 4 ms 8540 KB Correct: 5875 out of 25000 queries used.
28 Correct 4 ms 8540 KB Correct: 6221 out of 25000 queries used.
29 Correct 4 ms 8540 KB Correct: 6432 out of 25000 queries used.
30 Correct 5 ms 8536 KB Correct: 6707 out of 25000 queries used.
31 Correct 3 ms 8540 KB Correct: 6693 out of 25000 queries used.
32 Correct 4 ms 8540 KB Correct: 2979 out of 25000 queries used.
33 Correct 5 ms 8536 KB Correct: 6659 out of 25000 queries used.
34 Correct 4 ms 8540 KB Correct: 6657 out of 25000 queries used.
35 Correct 4 ms 8540 KB Correct: 6678 out of 25000 queries used.
36 Correct 3 ms 8792 KB Correct: 6729 out of 25000 queries used.
37 Correct 4 ms 8536 KB Correct: 6624 out of 25000 queries used.
38 Correct 3 ms 8540 KB Correct: 6756 out of 25000 queries used.
39 Correct 4 ms 8536 KB Correct: 6658 out of 25000 queries used.
40 Correct 4 ms 8540 KB Correct: 6712 out of 25000 queries used.
41 Correct 4 ms 8540 KB Correct: 6669 out of 25000 queries used.
42 Correct 3 ms 8592 KB Correct: 6681 out of 25000 queries used.
43 Correct 4 ms 8536 KB Correct: 2988 out of 25000 queries used.
44 Correct 4 ms 8540 KB Correct: 6609 out of 25000 queries used.
45 Correct 4 ms 8540 KB Correct: 6592 out of 25000 queries used.
46 Correct 4 ms 8540 KB Correct: 6606 out of 25000 queries used.
47 Correct 3 ms 8792 KB Correct: 6684 out of 25000 queries used.
48 Correct 3 ms 8540 KB Correct: 6735 out of 25000 queries used.
49 Correct 3 ms 8488 KB Correct: 6693 out of 25000 queries used.
50 Correct 3 ms 8536 KB Correct: 6689 out of 25000 queries used.
51 Correct 4 ms 8540 KB Correct: 6687 out of 25000 queries used.
52 Correct 3 ms 8540 KB Correct: 6667 out of 25000 queries used.
53 Correct 5 ms 8616 KB Correct: 6991 out of 25000 queries used.
54 Correct 7 ms 8540 KB Correct: 22053 out of 25000 queries used.
55 Correct 4 ms 8540 KB Correct: 6679 out of 25000 queries used.
56 Correct 5 ms 8536 KB Correct: 6735 out of 25000 queries used.
57 Correct 5 ms 8540 KB Correct: 7031 out of 25000 queries used.
58 Correct 3 ms 8540 KB Correct: 6604 out of 25000 queries used.
59 Correct 4 ms 8540 KB Correct: 6612 out of 25000 queries used.
60 Correct 6 ms 8540 KB Correct: 8431 out of 25000 queries used.
61 Correct 4 ms 8540 KB Correct: 7820 out of 25000 queries used.
62 Correct 4 ms 8540 KB Correct: 7211 out of 25000 queries used.
63 Correct 5 ms 8540 KB Correct: 7901 out of 25000 queries used.
64 Correct 6 ms 8540 KB Correct: 7466 out of 25000 queries used.
65 Correct 6 ms 8536 KB Correct: 10218 out of 25000 queries used.
66 Correct 4 ms 8540 KB Correct: 7353 out of 25000 queries used.
67 Correct 4 ms 8536 KB Correct: 3335 out of 25000 queries used.
68 Correct 7 ms 8540 KB Correct: 24867 out of 25000 queries used.
69 Correct 5 ms 8540 KB Correct: 15596 out of 25000 queries used.
70 Correct 5 ms 8540 KB Correct: 16349 out of 25000 queries used.