Submission #1239863

#TimeUsernameProblemLanguageResultExecution timeMemory
1239863new_accMin-max tree (BOI18_minmaxtree)C++20
22 / 100
79 ms24132 KiB
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int M=1e5+10;
const int SS=1<<20;
const int INFi=2e9;
const ll INFl=1e18;
const int mod=1e9+7;
const int p=70032301;
set<int> s[N];
int num[N],oj[N],pod[N],ans[N];
vi graf[N],dod[N];
void dfs(int v,int o){
    int pop=0;
    pod[v]=1;
    oj[v]=o;
    for(auto u:graf[v]){
        if(u==o) continue;
        dfs(u,v);
        if(pod[u]>pop){
            num[v]=num[u];
            pop=pod[u];
        }
        pod[v]+=pod[u];
    }
    for(auto u:graf[v]){
        if(u==o) continue; 
        if(num[v]!=num[u]){
            while(s[num[u]].size()){
                int val=*(s[num[u]].begin());
                s[num[u]].erase(val);
                auto it=s[num[v]].lower_bound(val);
                if(it!=s[num[v]].end() and (*it)==val) s[num[v]].erase(val);
                else s[num[v]].insert(val);
            }
        }
    }
    for(auto val:dod[v]){
        auto it=s[num[v]].lower_bound(val);
        if(it!=s[num[v]].end() and (*it)==val) s[num[v]].erase(val);
        else s[num[v]].insert(val);
    }
    if(s[num[v]].size()) ans[v]=*(s[num[v]].begin());
    else ans[v]=0;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        graf[a].push_back(b),graf[b].push_back(a);
    }
    int q;
    cin>>q;
    while(q--){
        char xd;
        int a,b,c;
        cin>>xd>>a>>b>>c;
        dod[a].push_back(c),dod[b].push_back(c);
    }
    for(int i=1;i<=n;i++) num[i]=i;
    dfs(1,1);
    for(int i=2;i<=n;i++){
        cout<<i<<" "<<oj[i]<<" "<<ans[i]<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...