oj.uz

Submission #111643

# Submission time Handle Problem Language Result Execution time Memory
111643 2019-05-15T23:15:55 Z discoverMeMe Factories (JOI14_factories) C++14
100 / 100
 3471 ms 108656 KB 
#include <bits/stdc++.h>
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

const int N=500001;
int n,cnt,st[N],ed[N],par[N][20],lvl[N],a,b,c,cand[N*2],ext[N],pcnt;
long long U[N],V[N],xx,len[N],MAX=LLONG_MAX>>2;
bool blc[N];
vector<pair<int,int>> gr[N];

int lca(int x,int y)
{
	if (lvl[x]>lvl[y])
        swap(x,y);
	int up=lvl[y]-lvl[x];
	ford(i,19,0)
        if(up&(1<<i))
            y=par[y][i];
	if (x==y)
        return x;
	for (int i=19;i>=0;i--)
		if (par[x][i]!=par[y][i])
		{
			x=par[x][i];
			y=par[y][i];
		}
	return par[x][0];
}
void dfs(int x)
{
	blc[x]=true;
	for (auto i:gr[x])
        if(!blc[i.first])
        {
            st[i.first]=++cnt; lvl[cnt]=lvl[st[x]]+1; len[cnt]=len[st[x]]+i.second; par[cnt][0]=st[x];
            forj(1,20)
                par[cnt][j]=par[par[cnt][j-1]][j-1];
            dfs(i.first);
        }
	ed[st[x]]=cnt;
}
void Init(int N,int A[],int B[],int D[])
{
	fori(0,N-1)
	{
		gr[A[i]].push_back({B[i],D[i]});
		gr[B[i]].push_back({A[i],D[i]});
	}
	st[0]=cnt=1;
	dfs(0);
}
int pdfs(int x)
{
	U[x]=V[x]=MAX;
	if(ext[cand[x]]==1)
        U[x]=0;
	if(ext[cand[x]]==2)
        V[x]=0;
	int e=x+1;
	while(e<pcnt&&cand[e]<=ed[cand[x]])
	{
		a=pdfs(e);
		U[x]=min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
		V[x]=min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
		e=a;
	}
	xx=min(xx,U[x]+V[x]);
	ext[cand[x]]=0;
	return e;
}

long long Query(int S,int X[],int T,int Y[])
{
	pcnt=0;
	for(int i=0;i<S;i++)
    {
        cand[pcnt++]=st[X[i]];
        ext[st[X[i]]]=1;
    }
	for(int i=0;i<T;i++)
    {
        cand[pcnt++]=st[Y[i]];
        ext[st[Y[i]]]=2;
    }
	sort(cand,cand+pcnt);
	for(int i=1;i<S+T;i++)
        cand[pcnt++]=lca(cand[i-1],cand[i]);
	sort(cand,cand+pcnt);
	pcnt=unique(cand,cand+pcnt)-cand;
	xx=MAX;
	pdfs(0);
	return xx;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12460 KB Output is correct
2 Correct 741 ms 21116 KB Output is correct
3 Correct 714 ms 20984 KB Output is correct
4 Correct 715 ms 21188 KB Output is correct
5 Correct 730 ms 21096 KB Output is correct
6 Correct 552 ms 21000 KB Output is correct
7 Correct 662 ms 20856 KB Output is correct
8 Correct 722 ms 21252 KB Output is correct
9 Correct 614 ms 21044 KB Output is correct
10 Correct 511 ms 21112 KB Output is correct
11 Correct 681 ms 21088 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 1501 ms 95072 KB Output is correct
3 Correct 1766 ms 94920 KB Output is correct
4 Correct 1266 ms 95792 KB Output is correct
5 Correct 2331 ms 105784 KB Output is correct
6 Correct 2570 ms 96332 KB Output is correct
7 Correct 1710 ms 36924 KB Output is correct
8 Correct 1100 ms 37864 KB Output is correct
9 Correct 1853 ms 38920 KB Output is correct
10 Correct 1732 ms 38320 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12460 KB Output is correct
2 Correct 741 ms 21116 KB Output is correct
3 Correct 714 ms 20984 KB Output is correct
4 Correct 715 ms 21188 KB Output is correct
5 Correct 730 ms 21096 KB Output is correct
6 Correct 552 ms 21000 KB Output is correct
7 Correct 662 ms 20856 KB Output is correct
8 Correct 722 ms 21252 KB Output is correct
9 Correct 614 ms 21044 KB Output is correct
10 Correct 511 ms 21112 KB Output is correct
11 Correct 681 ms 21088 KB Output is correct
12 Correct 14 ms 12288 KB Output is correct
13 Correct 1501 ms 95072 KB Output is correct
14 Correct 1766 ms 94920 KB Output is correct
15 Correct 1266 ms 95792 KB Output is correct
16 Correct 2331 ms 105784 KB Output is correct
17 Correct 2570 ms 96332 KB Output is correct
18 Correct 1710 ms 36924 KB Output is correct
19 Correct 1100 ms 37864 KB Output is correct
20 Correct 1853 ms 38920 KB Output is correct
21 Correct 1732 ms 38320 KB Output is correct
22 Correct 2227 ms 98984 KB Output is correct
23 Correct 2286 ms 101696 KB Output is correct
24 Correct 2136 ms 99956 KB Output is correct
25 Correct 2503 ms 103024 KB Output is correct
26 Correct 3231 ms 97232 KB Output is correct
27 Correct 2338 ms 108656 KB Output is correct
28 Correct 1540 ms 101936 KB Output is correct
29 Correct 3331 ms 97004 KB Output is correct
30 Correct 3471 ms 96892 KB Output is correct
31 Correct 2869 ms 97044 KB Output is correct
32 Correct 1002 ms 41676 KB Output is correct
33 Correct 714 ms 40300 KB Output is correct
34 Correct 1066 ms 35420 KB Output is correct
35 Correct 1412 ms 35356 KB Output is correct
36 Correct 1677 ms 35880 KB Output is correct
37 Correct 1627 ms 35868 KB Output is correct