oj.uz

Submission #68996

# Submission time Handle Problem Language Result Execution time Memory
68996 2018-08-19T12:24:30 Z istlemin Min-max tree (BOI18_minmaxtree) C++14
22 / 100
 784 ms 66028 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n;
vector<vi> e;

class LCA {
public:
	vector<vi> jump;
	vi p;
    vi levels;
	LCA() {

	}

    void init(){
		p.resize(n);
		levels.resize(n);
        dfs(0,0,0);
        jump.resize(30,vi(n));
        jump[0] = p;
        rep(i,1,30)
			rep(j,0,n)
				jump[i][j] = jump[i-1][jump[i-1][j]];
	}

	void dfs(ll v,ll last,ll level){
		p[v] = last;
		levels[v] = level;
		rep(i,0,e[v].size()){
			if(e[v][i]!=last)
				dfs(e[v][i],v,level+1);
		}
	}

    ll findLCA(ll a,ll b){
        if(levels[a]<levels[b]) swap(a,b);
        for(int i = 29;i>=0;i--){
            if(levels[jump[i][a]]>=levels[b])
				a = jump[i][a];
        }
        if(a==b) return a;
        for(int i = 29;i>=0;i--){
            if(jump[i][a]!=jump[i][b]){
				a = jump[i][a];
				b = jump[i][b];
			}
        }
		assert(a!=b);
		assert(p[a]==p[b]);
		return p[a];
    }
};

vector<vi> add;
vector<vi> rem;

vector<multiset<ll> > sets;

map<pii,ll> ans;

ll findWeights(ll v,ll last){
    ll maxes;
    if(e[v].size()==1&&last!=-1){
        maxes = sets.size();
        sets.emplace_back();
	} else {
		vi childMaxes;
		rep(i,0,e[v].size()){
			if(e[v][i]==last) continue;
			childMaxes.push_back(findWeights(e[v][i],v));
			if(sets[childMaxes[childMaxes.size()-1]].size()>0)
				ans[{v,e[v][i]}] = *sets[childMaxes[childMaxes.size()-1]].begin();
			else
				ans[{v,e[v][i]}] = 0;
		}
		maxes = childMaxes[0];
        rep(i,0,childMaxes.size()){
            if(sets[childMaxes[i]].size()>sets[maxes].size())
				maxes = childMaxes[i];
        }

        rep(i,0,childMaxes.size()){
            if(childMaxes[i]==maxes) continue;
			trav(mx,sets[childMaxes[i]])
				sets[maxes].insert(mx);
        }
	}
    rep(i,0,add[v].size())
		sets[maxes].insert(add[v][i]);
    rep(i,0,rem[v].size())
		sets[maxes].erase(sets[maxes].find(rem[v][i]));

	return maxes;
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n;
    e.resize(n);
    rem.resize(n);
    add.resize(n);
    rep(i,0,n-1){
		ll a,b;
		cin>>a>>b;
        --a; --b;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    LCA *lca = new LCA();
    lca->init();

    ll k;
    cin>>k;
    rep(i,0,k){
		char c;
        ll x,y,z;
        cin>>c>>x>>y>>z;
        assert(c=='M');
        --x;--y;

        ll lcaXY = lca->findLCA(x,y);
        rem[lcaXY].push_back(z);
        rem[lcaXY].push_back(z);
        add[x].push_back(z);
        add[y].push_back(z);
    }

    findWeights(0,-1);

    trav(edge,ans){
		cout<<edge.first.first+1<<" "<<edge.first.second+1<<" "<<edge.second<<endl;
    }

    _Exit(0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 44852 KB Output is correct
2 Correct 784 ms 50784 KB Output is correct
3 Correct 631 ms 50784 KB Output is correct
4 Correct 580 ms 51488 KB Output is correct
5 Correct 767 ms 53704 KB Output is correct
6 Correct 495 ms 53704 KB Output is correct
7 Correct 456 ms 53704 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 66028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -