oj.uz

Submission #25332

# Submission time Handle Problem Language Result Execution time Memory
25332 2017-06-21T07:44:10 Z 서규호(#1060) Factories (JOI14_factories) C++
Compilation error
 0 ms 0 KB 
#include "factories.h"
#include <bits/stdc++.h>

#define pb push_back
#define lld long long
#define Linf 1000000000000000000LL

using namespace std;

int N; lld ans;
int lev[500002];
pair<int,lld> par[500002][20];
int color[500002];
bool check[500002];
vector<pair<int,lld>> edge[500002];

void makepar(int x){
	check[x] = true;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		lev[i.first] = lev[x]+1;
		par[i.first][0].first = x; par[i.first][0].second = i.second;
		for(int j=1; j<=19; j++){
			par[i.first][j].first = par[par[i.first][j-1].first][j-1].first;
			par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
		}
		makepar(i.first);
	}
}

void Init(int n, int A[], int B[], int D[]) {
	N = n;
	for(int i=0; i<N-1; i++){
		A[i]++; B[i]++;
		edge[A[i]].pb({B[i],D[i]});
		edge[B[i]].pb({A[i],D[i]});
	}
	makepar(1);
}

pair<lld,lld> dfs(int x){
	check[x] = true;
	pair<lld,lld> tmp = {Linf,Linf};
	if(color[x] == 1) tmp.first = 0;
	else if(color[x] == 2) tmp.second = 0;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		pair<lld,lld> t = dfs(i.first);
		t.first += i.second; t.second += i.second;
		ans = min(ans,tmp.first+t.second);
		ans = min(ans,tmp.second+t.first);
		tmp.first = min(tmp.first,t.first);
		tmp.second= min(tmp.second,t.second);
	}
	return tmp;
}

int getpar(int x,int y){
	if(lev[x] > lev[y]) swap(x,y);
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		y = par[y][i].first;
	}
	if(x == y) return x;
	int t = -1;
	for(int i=0; i<=19; i++){
		if(par[x][i].first == par[y][i].first){
			t = i;
			break;
		}
	}
	if(t == -1) while(true);
	while(t != 0){
		t--;
		if(par[x][t] != par[y][t]){
			x = par[x][t].first;
			y = par[y][t].first;
		}
	}
	return par[x][0].first;
}
lld getdis(int x,int y){
	if(lev[x] > lev[y]) swap(x,y);
	lld tsum = 0;
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		tsum += par[y][i].second;
		y = par[y][i].first;
	}
	return tsum;
}

lld Query(int S, int X[], int T, int Y[]) {
	for(int i=0; i<S; i++) X[i]++;
	for(int i=0; i<T; i++) Y[i]++;
	if(S <= 10 && T <= 10){
		ans = Linf;
		for(int i=0; i<S; i++){
			for(int j=0; j<T; j++){
				int tmp = getpar(X[i],Y[j]);
				ans = min(ans,getdis(X[i],tmp)+getdis(Y[j],tmp));
				//printf("%d %d : %lld\n",X[i],Y[j],getdis(X[i],tmp)+getdis(Y[j],tmp));
			}
		}
		return ans;
	}
	for(int i=1; i<=N; i++){
		color[i] = 0;
		check[i] = false;
	}
	for(int i=0; i<S; i++) color[X[i]] = 1;
	for(int i=0; i<T; i++) color[Y[i]] = 2;
	ans = Linf;
	dfs(1);
	return ans;
}

Compilation message

factories.cpp:15:20: error: '>>' should be '> >' within a nested template argument list
 vector<pair<int,lld>> edge[500002];
                    ^
factories.cpp: In function 'void makepar(int)':
factories.cpp:19:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : edge[x]){
      ^
factories.cpp:19:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : edge[x]){
            ^
factories.cpp:19:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : edge[x]){
                ^
factories.cpp:20:14: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(check[i.first]) continue;
              ^
factories.cpp:21:9: error: request for member 'first' in 'i', which is of non-class type 'int'
   lev[i.first] = lev[x]+1;
         ^
factories.cpp:22:9: error: request for member 'first' in 'i', which is of non-class type 'int'
   par[i.first][0].first = x; par[i.first][0].second = i.second;
         ^
factories.cpp:22:36: error: request for member 'first' in 'i', which is of non-class type 'int'
   par[i.first][0].first = x; par[i.first][0].second = i.second;
                                    ^
factories.cpp:22:57: error: request for member 'second' in 'i', which is of non-class type 'int'
   par[i.first][0].first = x; par[i.first][0].second = i.second;
                                                         ^
factories.cpp:24:10: error: request for member 'first' in 'i', which is of non-class type 'int'
    par[i.first][j].first = par[par[i.first][j-1].first][j-1].first;
          ^
factories.cpp:24:38: error: request for member 'first' in 'i', which is of non-class type 'int'
    par[i.first][j].first = par[par[i.first][j-1].first][j-1].first;
                                      ^
factories.cpp:25:10: error: request for member 'first' in 'i', which is of non-class type 'int'
    par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
          ^
factories.cpp:25:39: error: request for member 'first' in 'i', which is of non-class type 'int'
    par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
                                       ^
factories.cpp:25:76: error: request for member 'first' in 'i', which is of non-class type 'int'
    par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
                                                                            ^
factories.cpp:27:13: error: request for member 'first' in 'i', which is of non-class type 'int'
   makepar(i.first);
             ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:35:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   edge[A[i]].pb({B[i],D[i]});
                 ^
factories.cpp:35:28: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   edge[A[i]].pb({B[i],D[i]});
                            ^
factories.cpp:36:17: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   edge[B[i]].pb({A[i],D[i]});
                 ^
factories.cpp:36:28: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
   edge[B[i]].pb({A[i],D[i]});
                            ^
factories.cpp: In function 'std::pair<long long int, long long int> dfs(int)':
factories.cpp:43:32: error: in C++98 'tmp' must be initialized by constructor, not by '{...}'
  pair<lld,lld> tmp = {Linf,Linf};
                                ^
factories.cpp:46:6: warning: 'auto' changes meaning in C++11; please remove it [-Wc++0x-compat]
  for(auto &i : edge[x]){
      ^
factories.cpp:46:12: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
  for(auto &i : edge[x]){
            ^
factories.cpp:46:16: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for(auto &i : edge[x]){
                ^
factories.cpp:47:14: error: request for member 'first' in 'i', which is of non-class type 'int'
   if(check[i.first]) continue;
              ^
factories.cpp:48:27: error: request for member 'first' in 'i', which is of non-class type 'int'
   pair<lld,lld> t = dfs(i.first);
                           ^
factories.cpp:49:16: error: request for member 'second' in 'i', which is of non-class type 'int'
   t.first += i.second; t.second += i.second;
                ^
factories.cpp:49:38: error: request for member 'second' in 'i', which is of non-class type 'int'
   t.first += i.second; t.second += i.second;
                                      ^