| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 486895 | 2021-11-13T08:54:03 Z | nikolapesic2802 | City Mapping (NOI18_citymapping) | C++14 | 75 ms | 32268 KB |
/*
-My idea is to go from vertex 1 to N and insert them in the right place in the graph.
-Sometimes this requires us to add some temporary vertexes, in my case i added them as vertexes with values greater than N. Later when i find out what vertex that is i put a map value to tell me what the real value of that vertex is
-I figured out the right place for every vertex by taking the diameter of the current tree, and figuring out where on the diameter the vertex is, and calling recursively for that subtree or adding it to the ends. We need to make sure not the explore the same vertexes 2 times too.
-Taking the diameter insures that the size of the next diameter is at most half of the current one so we get log n recursive calls.
*/
#include "citymapping.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
os << '{';
for(int i=0;i<sz(a);i++)
{
if(i>0&&i<sz(a))
os << ", ";
os << a[i]+1;
}
os << '}';
return os;
}
const int N=2e3+5;
const int offset=1e3+5;
vector<vector<int> > graf(N);
vector<int> blocke(N);
vector<int> mapa(N,-1);
ll dist[N][N];
int cnt=0;
void add_new(int n,int old,ll d)
{
graf[n].pb(old);
graf[old].pb(n);
for(int i=0;i<N;i++)
if(dist[old][i]!=-1)
dist[n][i]=dist[old][i]+d,dist[i][n]=dist[old][i]+d;
dist[n][old]=d;
dist[old][n]=d;
}
vector<int> v;
void dfs3(int tr,int par)
{
v.pb(tr);
for(auto p:graf[tr])
{
if(p==par)
continue;
dfs3(p,tr);
}
}
void add_between(int l,int r,int n,ll d)
{
v.clear();
dfs3(l,r);
for(auto p:v)
dist[n][p]=dist[l][p]+d,dist[p][n]=dist[l][p]+d;
v.clear();
dfs3(r,l);
for(auto p:v)
dist[n][p]=dist[r][p]+dist[l][r]-d,dist[p][n]=dist[r][p]+dist[l][r]-d;
for(int i=0;i<(int)graf[l].size();i++)
{
if(graf[l][i]==r)
{
graf[l].erase(graf[l].begin()+i);
break;
}
}
for(int i=0;i<(int)graf[r].size();i++)
{
if(graf[r][i]==l)
{
graf[r].erase(graf[r].begin()+i);
break;
}
}
graf[l].pb(n);
graf[n].pb(l);
graf[r].pb(n);
graf[n].pb(r);
dist[l][n]=d;
dist[n][l]=d;
dist[r][n]=dist[l][r]-d;
dist[n][r]=dist[l][r]-d;
}
ll ask(int x,int y)
{
if(dist[x][y]!=-1)
return dist[x][y];
if(x>=offset)
x=mapa[x];
if(y>=offset)
y=mapa[y];
return get_distance(x+1,y+1);
}
vector<int> vertex;
int maxx,koji;
void dfs(int tr,int d,int par)
{
if(maxx<d)
{
koji=tr;
maxx=d;
}
for(auto p:graf[tr])
{
if(p==par||blocke[p])
continue;
dfs(p,d+1,tr);
}
}
vector<int> stk;
void dfs2(int tr,int d,int par)
{
stk.pb(tr);
if(maxx==d)
{
vertex=stk;
maxx++;
}
for(auto p:graf[tr])
{
if(p==par||blocke[p])
continue;
dfs2(p,d+1,tr);
}
stk.pop_back();
}
void solve(int tr,int dodati)
{
maxx=0;
dfs(tr,1,-1);
maxx=0;
dfs(koji,1,-1);
stk.clear();
dfs2(koji,1,-1);
ll d1=ask(vertex.front(),dodati);
ll d2=ask(vertex.back(),dodati);
ll d=dist[vertex.front()][vertex.back()];
if(abs(d1-d2)==d)
{
if(d2>d1)
{
add_new(dodati,vertex.front(),d1);
}
else
{
add_new(dodati,vertex.back(),d2);
}
return;
}
ll s=d1+d2;
s-=dist[vertex.front()][vertex.back()];
s/=2;
d1-=s;
d2-=s;
int l=0,r=vertex.size()-1;
while(r-l>1)
{
int mid=(l+r)>>1;
if(dist[vertex[l]][vertex[mid]]>=d1)
{
d2-=dist[vertex[r]][vertex[mid]];
r=mid;
}
else
{
d1-=dist[vertex[l]][vertex[mid]];
l=mid;
}
}
if(d1==0)
{
if(s==0)
{
mapa[vertex[l]]=dodati;
return;
}
if(graf[vertex[l]].size()<3)
{
add_new(dodati,vertex[l],s);
return;
}
blocke[vertex[l-1]]=1;
blocke[vertex[l+1]]=1;
dist[vertex[l]][dodati]=s;
dist[dodati][vertex[l]]=s;
solve(vertex[l],dodati);
return;
}
if(d2==0)
{
if(s==0)
{
mapa[vertex[r]]=dodati;
return;
}
if(graf[vertex[r]].size()<3)
{
add_new(dodati,vertex[r],s);
return;
}
blocke[vertex[r-1]]=1;
blocke[vertex[r+1]]=1;
dist[vertex[r]][dodati]=s;
dist[dodati][vertex[r]]=s;
solve(vertex[r],dodati);
return;
}
if(s==0)
{
add_between(vertex[l],vertex[r],dodati,d1);
return;
}
int tt=offset+cnt;
cnt++;
add_between(vertex[l],vertex[r],tt,d1);
add_new(dodati,tt,s);
}
void find_roads(int n, int Q, int A[], int B[], int W[]) {
memset(dist,-1,sizeof(dist));
ll a=get_distance(1,2);
add_new(1,0,a);
for(int i=2;i<n;i++)
{
fill(blocke.begin(),blocke.end(),0);
solve(0,i);
}
int num=0;
vector<int> visited(N);
queue<int> q;
q.push(0);
visited[0]=1;
while(q.size())
{
int tr=q.front();
q.pop();
for(auto p:graf[tr])
{
if(visited[p])
continue;
if(tr>=offset)
A[num]=mapa[tr]+1;
else
A[num]=tr+1;
if(p>=offset)
B[num]=mapa[p]+1;
else
B[num]=p+1;
W[num]=dist[tr][p];
num++;
visited[p]=1;
q.push(p);
}
}
return;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 53 ms | 32144 KB | Correct: 1995 out of 500000 queries used. |
| 2 | Correct | 43 ms | 32100 KB | Correct: 2004 out of 500000 queries used. |
| 3 | Correct | 45 ms | 31992 KB | Correct: 5135 out of 500000 queries used. |
| 4 | Correct | 41 ms | 31992 KB | Correct: 5802 out of 500000 queries used. |
| 5 | Correct | 68 ms | 32004 KB | Correct: 5160 out of 500000 queries used. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 53 ms | 32144 KB | Correct: 1995 out of 500000 queries used. |
| 2 | Correct | 43 ms | 32100 KB | Correct: 2004 out of 500000 queries used. |
| 3 | Correct | 45 ms | 31992 KB | Correct: 5135 out of 500000 queries used. |
| 4 | Correct | 41 ms | 31992 KB | Correct: 5802 out of 500000 queries used. |
| 5 | Correct | 68 ms | 32004 KB | Correct: 5160 out of 500000 queries used. |
| 6 | Correct | 49 ms | 32124 KB | Correct: 1989 out of 500000 queries used. |
| 7 | Correct | 41 ms | 32116 KB | Correct: 1996 out of 500000 queries used. |
| 8 | Correct | 42 ms | 32012 KB | Correct: 5211 out of 500000 queries used. |
| 9 | Correct | 38 ms | 31996 KB | Correct: 5824 out of 500000 queries used. |
| 10 | Correct | 75 ms | 32268 KB | Correct: 5201 out of 500000 queries used. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 49 ms | 32080 KB | Correct: 1979 out of 12000 queries used. |
| 2 | Correct | 52 ms | 32100 KB | Correct: 1983 out of 12000 queries used. |
| 3 | Correct | 60 ms | 32152 KB | Correct: 1997 out of 12000 queries used. |
| 4 | Correct | 48 ms | 32124 KB | Correct: 1983 out of 12000 queries used. |
| 5 | Correct | 57 ms | 32100 KB | Correct: 1979 out of 12000 queries used. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 49 ms | 32080 KB | Correct: 1979 out of 12000 queries used. |
| 2 | Correct | 52 ms | 32100 KB | Correct: 1983 out of 12000 queries used. |
| 3 | Correct | 60 ms | 32152 KB | Correct: 1997 out of 12000 queries used. |
| 4 | Correct | 48 ms | 32124 KB | Correct: 1983 out of 12000 queries used. |
| 5 | Correct | 57 ms | 32100 KB | Correct: 1979 out of 12000 queries used. |
| 6 | Correct | 54 ms | 32144 KB | Correct: 1993 out of 12000 queries used. |
| 7 | Correct | 47 ms | 32116 KB | Correct: 1989 out of 12000 queries used. |
| 8 | Correct | 49 ms | 32144 KB | Correct: 1997 out of 12000 queries used. |
| 9 | Correct | 47 ms | 32076 KB | Correct: 1991 out of 12000 queries used. |
| 10 | Correct | 46 ms | 32152 KB | Correct: 1985 out of 12000 queries used. |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 53 ms | 32144 KB | Correct: 1995 out of 500000 queries used. |
| 2 | Correct | 43 ms | 32100 KB | Correct: 2004 out of 500000 queries used. |
| 3 | Correct | 45 ms | 31992 KB | Correct: 5135 out of 500000 queries used. |
| 4 | Correct | 41 ms | 31992 KB | Correct: 5802 out of 500000 queries used. |
| 5 | Correct | 68 ms | 32004 KB | Correct: 5160 out of 500000 queries used. |
| 6 | Correct | 49 ms | 32124 KB | Correct: 1989 out of 500000 queries used. |
| 7 | Correct | 41 ms | 32116 KB | Correct: 1996 out of 500000 queries used. |
| 8 | Correct | 42 ms | 32012 KB | Correct: 5211 out of 500000 queries used. |
| 9 | Correct | 38 ms | 31996 KB | Correct: 5824 out of 500000 queries used. |
| 10 | Correct | 75 ms | 32268 KB | Correct: 5201 out of 500000 queries used. |
| 11 | Correct | 49 ms | 32080 KB | Correct: 1979 out of 12000 queries used. |
| 12 | Correct | 52 ms | 32100 KB | Correct: 1983 out of 12000 queries used. |
| 13 | Correct | 60 ms | 32152 KB | Correct: 1997 out of 12000 queries used. |
| 14 | Correct | 48 ms | 32124 KB | Correct: 1983 out of 12000 queries used. |
| 15 | Correct | 57 ms | 32100 KB | Correct: 1979 out of 12000 queries used. |
| 16 | Correct | 54 ms | 32144 KB | Correct: 1993 out of 12000 queries used. |
| 17 | Correct | 47 ms | 32116 KB | Correct: 1989 out of 12000 queries used. |
| 18 | Correct | 49 ms | 32144 KB | Correct: 1997 out of 12000 queries used. |
| 19 | Correct | 47 ms | 32076 KB | Correct: 1991 out of 12000 queries used. |
| 20 | Correct | 46 ms | 32152 KB | Correct: 1985 out of 12000 queries used. |
| 21 | Correct | 51 ms | 32084 KB | Correct: 1989 out of 25000 queries used. |
| 22 | Correct | 40 ms | 32060 KB | Correct: 2002 out of 25000 queries used. |
| 23 | Correct | 43 ms | 32132 KB | Correct: 1986 out of 25000 queries used. |
| 24 | Correct | 38 ms | 32076 KB | Correct: 1983 out of 25000 queries used. |
| 25 | Correct | 40 ms | 31948 KB | Correct: 5021 out of 25000 queries used. |
| 26 | Correct | 39 ms | 31948 KB | Correct: 4913 out of 25000 queries used. |
| 27 | Correct | 40 ms | 31984 KB | Correct: 5072 out of 25000 queries used. |
| 28 | Correct | 43 ms | 32000 KB | Correct: 5157 out of 25000 queries used. |
| 29 | Correct | 41 ms | 32008 KB | Correct: 5036 out of 25000 queries used. |
| 30 | Correct | 41 ms | 31980 KB | Correct: 5037 out of 25000 queries used. |
| 31 | Correct | 38 ms | 31948 KB | Correct: 5829 out of 25000 queries used. |
| 32 | Correct | 47 ms | 32076 KB | Correct: 1987 out of 25000 queries used. |
| 33 | Correct | 38 ms | 31948 KB | Correct: 5795 out of 25000 queries used. |
| 34 | Correct | 41 ms | 32020 KB | Correct: 5849 out of 25000 queries used. |
| 35 | Correct | 39 ms | 31948 KB | Correct: 5858 out of 25000 queries used. |
| 36 | Correct | 37 ms | 32032 KB | Correct: 5810 out of 25000 queries used. |
| 37 | Correct | 38 ms | 31948 KB | Correct: 5793 out of 25000 queries used. |
| 38 | Correct | 37 ms | 32004 KB | Correct: 5868 out of 25000 queries used. |
| 39 | Correct | 38 ms | 31948 KB | Correct: 5851 out of 25000 queries used. |
| 40 | Correct | 37 ms | 32004 KB | Correct: 5794 out of 25000 queries used. |
| 41 | Correct | 38 ms | 32004 KB | Correct: 5772 out of 25000 queries used. |
| 42 | Correct | 38 ms | 32000 KB | Correct: 5803 out of 25000 queries used. |
| 43 | Correct | 48 ms | 32152 KB | Correct: 1993 out of 25000 queries used. |
| 44 | Correct | 42 ms | 32072 KB | Correct: 5823 out of 25000 queries used. |
| 45 | Correct | 38 ms | 32008 KB | Correct: 5754 out of 25000 queries used. |
| 46 | Correct | 37 ms | 32012 KB | Correct: 5772 out of 25000 queries used. |
| 47 | Correct | 39 ms | 32000 KB | Correct: 5770 out of 25000 queries used. |
| 48 | Correct | 38 ms | 31948 KB | Correct: 5869 out of 25000 queries used. |
| 49 | Correct | 38 ms | 32020 KB | Correct: 5810 out of 25000 queries used. |
| 50 | Correct | 37 ms | 31948 KB | Correct: 5823 out of 25000 queries used. |
| 51 | Correct | 38 ms | 31948 KB | Correct: 5813 out of 25000 queries used. |
| 52 | Correct | 37 ms | 32008 KB | Correct: 5868 out of 25000 queries used. |
| 53 | Correct | 42 ms | 32000 KB | Correct: 5877 out of 25000 queries used. |
| 54 | Correct | 39 ms | 32116 KB | Correct: 2001 out of 25000 queries used. |
| 55 | Correct | 39 ms | 31992 KB | Correct: 5866 out of 25000 queries used. |
| 56 | Correct | 38 ms | 31996 KB | Correct: 5791 out of 25000 queries used. |
| 57 | Correct | 39 ms | 31948 KB | Correct: 5775 out of 25000 queries used. |
| 58 | Correct | 37 ms | 32012 KB | Correct: 5754 out of 25000 queries used. |
| 59 | Correct | 38 ms | 32000 KB | Correct: 5815 out of 25000 queries used. |
| 60 | Correct | 58 ms | 32012 KB | Correct: 4531 out of 25000 queries used. |
| 61 | Correct | 59 ms | 31940 KB | Correct: 4459 out of 25000 queries used. |
| 62 | Correct | 64 ms | 32008 KB | Correct: 4976 out of 25000 queries used. |
| 63 | Correct | 63 ms | 32260 KB | Correct: 4873 out of 25000 queries used. |
| 64 | Correct | 59 ms | 32016 KB | Correct: 4411 out of 25000 queries used. |
| 65 | Correct | 40 ms | 32124 KB | Correct: 1982 out of 25000 queries used. |
| 66 | Correct | 63 ms | 31992 KB | Correct: 5004 out of 25000 queries used. |
| 67 | Correct | 40 ms | 32076 KB | Correct: 1987 out of 25000 queries used. |
| 68 | Correct | 39 ms | 32076 KB | Correct: 1985 out of 25000 queries used. |
| 69 | Correct | 39 ms | 32120 KB | Correct: 1998 out of 25000 queries used. |
| 70 | Correct | 39 ms | 32092 KB | Correct: 1989 out of 25000 queries used. |