답안 #97406 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97406	2019-02-15T18:34:01 Z	igzi	공장들 (JOI14_factories)	C++17	100 / 100	3488 ms	194692 KB

factories

#include <bits/stdc++.h>
#define INF 100000000000000000
#include "factories.h"
#define maxN 500005

using namespace std;

vector <int> e;
vector <pair<int,int>> adj[maxN];

long long n,d[maxN],p[maxN],pos[maxN],l[2*maxN],dis[maxN],ds[2][maxN];
int s[22][2*maxN],sx[22][maxN],sy[22][maxN];

void dfs(int n,int par){
e.push_back(n);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i].first==par) continue;
dis[adj[n][i].first]=dis[n]+adj[n][i].second;
d[adj[n][i].first]=d[n]+1;
dfs(adj[n][i].first,n);
e.push_back(n);
}
}

int minimum(int a,int b){
if(d[a]<d[b]) return a;
return b;
}

void Init(int N,int a[],int b[],int D[]){
n=N;
int i,j;
for(i=0;i<n-1;i++){
adj[a[i]].push_back({b[i],D[i]});
adj[b[i]].push_back({a[i],D[i]});
}
d[0]=0;
dis[0]=0;
dfs(0,-1);
l[1]=0;
for(i=0;i<n;i++){
p[i]=-1;
}
for(i=0;i<e.size();i++){
if(p[e[i]]==-1) p[e[i]]=i;
pos[e[i]]=i;
s[0][i]=e[i];
if(i<2) continue;
if(i==(i & -i)) l[i]=l[i-1]+1;
else l[i]=l[i-1];
}
for(j=1;j<21;j++){
for(i=0;i<e.size();i++){
    if(i+(1<<j)>e.size()) continue;
    s[j][i]=minimum(s[j-1][i],s[j-1][i+(1<<(j-1))]);
}
}
}

int minimum2(int a,int b){
if(dis[a]<dis[b]) return a;
return b;
}

long long Query(int S,int x[],int T,int y[]){
long long ans=INF;
vector <int> lca,v,X,Y;
int i,j,a,b,tmp,len,pom;
for(i=0;i<S;i++) {v.push_back(p[x[i]]); X.push_back(p[x[i]]);}
for(i=0;i<T;i++) {v.push_back(p[y[i]]); Y.push_back(p[y[i]]);}
sort(v.begin(),v.end());
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
for(i=1;i<v.size();i++){
    a=v[i-1];
    b=v[i];
    len=b-a+1;
    tmp=minimum(s[l[len]][a],s[l[len]][b-(1<<l[len])+1]);
    lca.push_back(tmp);
}
for(i=0;i<S;i++){
sx[0][i]=e[X[i]];
}
for(j=1;(1<<j)<=S;j++){
for(i=0;i<S;i++){
    if(i+(1<<j)>S) continue;
    sx[j][i]=minimum2(sx[j-1][i],sx[j-1][i+(1<<(j-1))]);
}
}
for(i=0;i<T;i++){
sy[0][i]=e[Y[i]];
}
for(j=1;(1<<j)<=T;j++){
for(i=0;i<T;i++){
    if(i+(1<<j)>T) continue;
    sy[j][i]=minimum2(sy[j-1][i],sy[j-1][i+(1<<(j-1))]);
}
}
for(i=0;i<lca.size();i++){
    a=lower_bound(X.begin(),X.end(),p[lca[i]])-X.begin();
    b=lower_bound(X.begin(),X.end(),pos[lca[i]]+1)-X.begin()-1;
    if(b<a) continue;
    len=b-a+1;
    tmp=minimum2(sx[l[len]][a],sx[l[len]][b-(1<<l[len])+1]);
    a=lower_bound(Y.begin(),Y.end(),p[lca[i]])-Y.begin();
    b=lower_bound(Y.begin(),Y.end(),pos[lca[i]]+1)-Y.begin()-1;
    if(b<a) continue;
    len=b-a+1;
    pom=minimum2(sy[l[len]][a],sy[l[len]][b-(1<<l[len])+1]);
    ans=min(ans,dis[tmp]+dis[pom]-2*dis[lca[i]]);
}
return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:53:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i+(1<<j)>e.size()) continue;
        ~~~~~~~~^~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:74:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=1;i<v.size();i++){
         ~^~~~~~~~~
factories.cpp:99:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<lca.size();i++){
         ~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	12672 KB	Output is correct
2	Correct	898 ms	21624 KB	Output is correct
3	Correct	897 ms	21772 KB	Output is correct
4	Correct	709 ms	22088 KB	Output is correct
5	Correct	797 ms	22072 KB	Output is correct
6	Correct	727 ms	21812 KB	Output is correct
7	Correct	903 ms	21752 KB	Output is correct
8	Correct	860 ms	22028 KB	Output is correct
9	Correct	837 ms	21856 KB	Output is correct
10	Correct	721 ms	21880 KB	Output is correct
11	Correct	853 ms	21752 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	12416 KB	Output is correct
2	Correct	1734 ms	145484 KB	Output is correct
3	Correct	2000 ms	146112 KB	Output is correct
4	Correct	1462 ms	146316 KB	Output is correct
5	Correct	2414 ms	163004 KB	Output is correct
6	Correct	2098 ms	147576 KB	Output is correct
7	Correct	1404 ms	45588 KB	Output is correct
8	Correct	1357 ms	46572 KB	Output is correct
9	Correct	1628 ms	48488 KB	Output is correct
10	Correct	1534 ms	47148 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	12672 KB	Output is correct
2	Correct	898 ms	21624 KB	Output is correct
3	Correct	897 ms	21772 KB	Output is correct
4	Correct	709 ms	22088 KB	Output is correct
5	Correct	797 ms	22072 KB	Output is correct
6	Correct	727 ms	21812 KB	Output is correct
7	Correct	903 ms	21752 KB	Output is correct
8	Correct	860 ms	22028 KB	Output is correct
9	Correct	837 ms	21856 KB	Output is correct
10	Correct	721 ms	21880 KB	Output is correct
11	Correct	853 ms	21752 KB	Output is correct
12	Correct	21 ms	12416 KB	Output is correct
13	Correct	1734 ms	145484 KB	Output is correct
14	Correct	2000 ms	146112 KB	Output is correct
15	Correct	1462 ms	146316 KB	Output is correct
16	Correct	2414 ms	163004 KB	Output is correct
17	Correct	2098 ms	147576 KB	Output is correct
18	Correct	1404 ms	45588 KB	Output is correct
19	Correct	1357 ms	46572 KB	Output is correct
20	Correct	1628 ms	48488 KB	Output is correct
21	Correct	1534 ms	47148 KB	Output is correct
22	Correct	2890 ms	154384 KB	Output is correct
23	Correct	2427 ms	156796 KB	Output is correct
24	Correct	3347 ms	155704 KB	Output is correct
25	Correct	3208 ms	159136 KB	Output is correct
26	Correct	2834 ms	148648 KB	Output is correct
27	Correct	3488 ms	194692 KB	Output is correct
28	Correct	1974 ms	182488 KB	Output is correct
29	Correct	2710 ms	172584 KB	Output is correct
30	Correct	2812 ms	172128 KB	Output is correct
31	Correct	3106 ms	172588 KB	Output is correct
32	Correct	1825 ms	68812 KB	Output is correct
33	Correct	1368 ms	66884 KB	Output is correct
34	Correct	1559 ms	57808 KB	Output is correct
35	Correct	1505 ms	57724 KB	Output is correct
36	Correct	1648 ms	58032 KB	Output is correct
37	Correct	1721 ms	58080 KB	Output is correct

답안 #97406

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 18.0 / 18.0

Subtask #3 67.0 / 67.0

Subtask #1
15.0 / 15.0

Subtask #2
18.0 / 18.0

Subtask #3
67.0 / 67.0