結果

問題 No.912 赤黒木
ユーザー latte0119latte0119
提出日時 2019-10-18 23:11:19
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,995 bytes
コンパイル時間 2,811 ms
コンパイル使用メモリ 171,516 KB
実行使用メモリ 68,724 KB
最終ジャッジ日時 2024-06-25 19:09:33
合計ジャッジ時間 13,057 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
19,148 KB
testcase_01 AC 9 ms
19,152 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 333 ms
53,324 KB
testcase_23 AC 337 ms
47,988 KB
testcase_24 AC 338 ms
47,096 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 487 ms
67,148 KB
testcase_29 AC 492 ms
67,020 KB
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:175:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  175 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
main.cpp:178:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  178 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:185:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  185 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

template<typename I,bool isMin>
struct ConvexHullTrick{
#define a first
#define b second
 
	using Line=pair<I,I>;
	deque<Line>lines;
 
	//l.a>=m.a>=r.a
	inline bool notNecessary(const Line &l,const Line &m,const Line &r){
		return (m.a-l.a)*(r.b-m.b)>=(m.b-l.b)*(r.a-m.a);
	}
	void addLine(I a,I b){
		if(!isMin)a*=-1,b*=-1;
		Line l(a,b);
		if(lines.empty())lines.push_back(l);
		else if(lines.front().a<=a){
			if(lines.front().a==a){
				if(lines.front().b<=b)return;
				lines.pop_front();
			}
			while(lines.size()>=2&&notNecessary(l,lines[0],lines[1]))lines.pop_front();
			lines.push_front(l);
		}
		else{
			if(lines.back().a==a){
				if(lines.back().b<=b)return;
				lines.pop_back();
			}
			while(lines.size()>=2&&notNecessary(lines[lines.size()-2],lines[lines.size()-1],l))lines.pop_back();
			lines.push_back(l);
		}
	}
 
	inline I eval(const Line &l,I x){
		return l.a*x+l.b;
	}
 
	I query(I x){
		int lb=-1,ub=lines.size()-1;
		while(ub-lb>1){
			int mid=(ub+lb)/2;
			if(eval(lines[mid],x)<=eval(lines[mid+1],x))ub=mid;
			else lb=mid;
		}
		if(isMin)return eval(lines[ub],x);
		return -eval(lines[ub],x);
	}
 
	I queryMonotoneInc(I x){
		while(lines.size()>=2&&eval(lines[0],x)>=eval(lines[1],x))lines.pop_front();
		if(isMin)return eval(lines[0],x);
		return -eval(lines[0],x);
	}
	I queryMonotoneDec(I x){
		while(lines.size()>=2&&eval(lines[lines.size()-1],x)>=eval(lines[lines.size()-2],x))lines.pop_back();
		if(isMin)return eval(lines.back(),x);
		return -eval(lines.back(),x);
	}
#undef a
#undef b
};

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n=0){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};



int N;
vint G[222222];
vint lis[222222];

int ans;
UnionFindTree uf;

vpint uku[222222];

void add(vpint &vec,pint p){
    if(vec.size()==0){
        vec.pb(p);
    }
    else{
        pint q=vec.back();

        if(uf.areSame(p.se,q.se)){
            vec.pb(p);
            if(vec[0].fi<vec[1].fi)swap(vec[0],vec[1]);
        }
        else{
            uf.unite(p.se,q.se);
            vec.pop_back();
            ans+=p.fi+q.fi;
        }
    }
}

void dfs(int v,int p){

    vpint vec;
    for(auto x:lis[v])vec.pb(pint(0,x));
    for(auto u:G[v]){
        if(u==p)continue;
        dfs(u,v);
        rep(i,uku[u].size()){
            pint p=uku[u][i];
            p.fi++;
            vec.pb(p);
        }
    }

    
    sort(all(vec));
    rep(i,vec.size())add(uku[v],vec[i]);
}
signed main(){
    scanf("%lld",&N);
    rep(i,N-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }

    rep(i,N-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        lis[a].pb(i);lis[b].pb(i);
    }
    uf=UnionFindTree(N-1);

    ans=N-1;
    dfs(0,-1);
    cout<<ans<<endl;
    return 0;
}
0