# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
318971 |
2020-11-03T15:25:07 Z |
Dymo |
Factories (JOI14_factories) |
C++14 |
|
1058 ms |
27620 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e4+54;
const ll mod =1e9+7 ;
const ll base=1e18;
vector<pll> adj[maxn];
int dep[maxn];
ll dep1[maxn];
int anc[maxn][20];
int col[maxn];
vector<ll> adj1[maxn];
int f[maxn];
int l[maxn];
int cnt=0;
void dfs(ll u,ll par)
{
cnt++;
f[u]=cnt;
anc[u][0]=par;
for (int i=1;i<19;i++)
{
anc[u][i]=anc[anc[u][i-1]][i-1];
}
for (auto to:adj[u])
{
if (to.ff==par) continue;
dep[to.ff]=dep[u]+1;
dep1[to.ff]=dep1[u]+to.ss;
dfs(to.ff,u);
}
l[u]=cnt;
}
ll lca(ll x,ll y)
{
if (dep[x]< dep[y]) swap(x,y);
ll kc= dep[x]-dep[y];
for (int i=18;i>=0;i--)
{
if (kc&(1ll<<i))
{
x=anc[x][i];
}
}
if (x==y) return x;
for (int i=18;i>=0;i--)
{
if (anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
ll kc(ll x,ll y)
{
return dep1[x]+dep1[y]-2*(dep1[lca(x,y)]);
}
ll dp1[maxn];
ll dp2[maxn];
ll ans=1e18;
void dfs1(ll u)
{
dp1[u]=dp2[u]=1e15;
if (col[u]==1) dp1[u]=dep1[u];
else if (col[u]==2) dp2[u]=dep1[u];
for (auto to:adj1[u])
{
dfs1(to);
ans=min(ans,dp1[u]+dp2[to]-dep1[u]*2);
ans=min(ans,dp2[u]+dp1[to]-dep1[u]*2);
dp1[u]=min(dp1[u],dp1[to]);
dp2[u]=min(dp2[u],dp2[to]);
}
}
void Init(int N,int A[],int B[],int D[])
{
ll n= N;
for (int i=1;i<=n;i++)
{
adj[i].clear();
}
for (int i=0;i<n-1;i++)
{
A[i]++;
B[i]++;
adj[A[i]].pb(make_pair(B[i],D[i]));
adj[B[i]].pb(make_pair(A[i],D[i]));
}
cnt=0;
dfs(1,0);
for (int i=1;i<=n;i++)
{
adj[i].clear();
}
}
long long Query(int S,int X[],int T,int Y[])
{
ans=1e18;
vector<pll> vt;
for (int i=0;i<S;i++)
{
X[i]++;
col[X[i]]=1;
vt.pb(make_pair(f[X[i]],X[i]));
}
for (int i=0;i<T;i++)
{
Y[i]++;
col[Y[i]]=2;
vt.pb(make_pair(f[Y[i]],Y[i]));
}
sort(vt.begin(),vt.end());
vector<pll> nw;
for (int i=1;i<vt.size();i++)
{
ll h=lca(vt[i].ss,vt[i-1].ss);
nw.pb(make_pair(f[h],h));
}
for (auto p:vt)
{
nw.pb(p);
}
nw.pb(make_pair(f[1],1));
sort(nw.begin(),nw.end());
nw.resize(unique(nw.begin(),nw.end())-nw.begin());
stack<ll> st;
for (auto p:nw)
{
while (st.size()&&l[st.top()]<p.ff) st.pop();
if (st.size())
{
adj1[st.top()].pb(p.ss);
}
st.push(p.ss);
}
dfs1(1);
for (auto p:nw)
{
col[p.ss]=0;
adj1[p.ss].clear();
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.txt", "r"))
{
freopen("test.txt", "r", stdin);
// freopen("team.out", "w", stdout);
}
}*/
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:131:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int i=1;i<vt.size();i++)
| ~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3180 KB |
Output is correct |
2 |
Correct |
1058 ms |
12348 KB |
Output is correct |
3 |
Correct |
998 ms |
12260 KB |
Output is correct |
4 |
Correct |
1010 ms |
12432 KB |
Output is correct |
5 |
Correct |
927 ms |
12588 KB |
Output is correct |
6 |
Correct |
831 ms |
12308 KB |
Output is correct |
7 |
Correct |
992 ms |
12132 KB |
Output is correct |
8 |
Correct |
1014 ms |
12444 KB |
Output is correct |
9 |
Correct |
917 ms |
12520 KB |
Output is correct |
10 |
Correct |
825 ms |
12204 KB |
Output is correct |
11 |
Correct |
1030 ms |
11972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
2924 KB |
Output is correct |
2 |
Runtime error |
386 ms |
27620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
3180 KB |
Output is correct |
2 |
Correct |
1058 ms |
12348 KB |
Output is correct |
3 |
Correct |
998 ms |
12260 KB |
Output is correct |
4 |
Correct |
1010 ms |
12432 KB |
Output is correct |
5 |
Correct |
927 ms |
12588 KB |
Output is correct |
6 |
Correct |
831 ms |
12308 KB |
Output is correct |
7 |
Correct |
992 ms |
12132 KB |
Output is correct |
8 |
Correct |
1014 ms |
12444 KB |
Output is correct |
9 |
Correct |
917 ms |
12520 KB |
Output is correct |
10 |
Correct |
825 ms |
12204 KB |
Output is correct |
11 |
Correct |
1030 ms |
11972 KB |
Output is correct |
12 |
Correct |
6 ms |
2924 KB |
Output is correct |
13 |
Runtime error |
386 ms |
27620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
14 |
Halted |
0 ms |
0 KB |
- |