제출 #96182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96182		mnbv	Min-max tree (BOI18_minmaxtree)	C++14	0 / 100	302 ms	45416 KiB

minmaxtree

#include <bits/stdc++.h>
#define maxN 70007

using namespace std;

struct cvor{
int c,d,s,val,par,p;
};
struct segment{
int l,v;
};

cvor a[maxN];
vector <int> adj[maxN],v[maxN];
vector <segment> seg[maxN];
int n,m,i,j,x,y,c=0,t[maxN];

void dfs(int n){
a[n].s=1;
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
a[adj[n][i]].par=n;
a[adj[n][i]].d=a[n].d+1;
dfs(adj[n][i]);
a[n].s+=a[adj[n][i]].s;
}
}

void dodela(int n){
a[n].c=c;
a[n].p=v[c].size();
v[c].push_back(n);
if(n!=0 && adj[n].size()==1) {c++; return;}
int tmp,m=0;
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
if(a[adj[n][i]].s>m) {m=a[adj[n][i]].s; tmp=adj[n][i];}
}
//cout<<n<<" "<<tmp<<endl;
dodela(tmp);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par || adj[n][i]==tmp) continue;
t[c]=adj[n][i];
dodela(adj[n][i]);
}
}

vector <int> _merge(vector <int> a,vector <int> b){
vector <int> ans;
int i,j;
i=0; j=0;
while(i<a.size() && j<b.size()){
if(a[i]<b[j]) {ans.push_back(a[i]); i++;}
else {ans.push_back(b[j]); j++;}
}
while(i<a.size()){ans.push_back(a[i]); i++;}
while(j<b.size()){ans.push_back(b[j]); j++;}
return ans;
}

void propagate(int x,int n,int l,int d){
if(seg[x][n].l==0) return;
if(l==d){
    seg[x][n].v=seg[x][n].l;
    seg[x][n].l=0;
    return;
}
seg[x][2*n].l=seg[x][2*n+1].l=seg[x][n].l;
seg[x][n].l=0;
}

void update(int x,int n,int l,int d,int a,int b,int v){
propagate(x,n,l,d);
if(l>=a && d<=b){seg[x][n].l=v; return;}
int m=(l+d)/2;
if(a<=m) update(x,2*n,l,m,a,b,v);
if(b>=m+1) update(x,2*n+1,m+1,d,a,b,v);
seg[x][n].v=max(seg[x][2*n].v,seg[x][2*n+1].v);
}

int query(int x,int n,int l,int d,int y){
propagate(x,n,l,d);
if(l==d) return seg[x][n].v;
int m=(l+d)/2;
if(y<=m) return query(x,2*n,l,m,y);
return query(x,2*n+1,m+1,d,y);
}

vector <int> e;
int p[maxN];
pair<int,int> spar[2*maxN][22];

void ojler(int n){
e.push_back(n);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i]==a[n].par) continue;
ojler(adj[n][i]);
e.push_back(n);
}
}

void upd(int x,int y,int val){
if(a[x].d<=a[y].d) return;
int tmp=t[a[x].c];
if(a[tmp].d>a[y].d){
    update(a[x].c,1,0,v[a[x].c].size()-1,0,a[x].p,val);
    upd(a[tmp].par,y,val);
    return;
}
update(a[x].c,1,0,v[a[x].c].size()-1,a[y].p,a[x].p,val);
}

struct uslov{
int a,b,v;
};

vector <uslov> u;
uslov pom;

bool poredi(uslov a,uslov b){
return a.v>b.v;
}

int lca(int x,int y){
pair<int,int> tmp={maxN,maxN};
for(int j = 21; j >= 0; j--) {
    if(x + (1 << j) - 1 <= y) {
        tmp = min(tmp, spar[x][j]);
        x += 1 << j;
    }
}
return tmp.second;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<n;i++){
        cin>>x>>y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    a[0].par=-1;
    dfs(0);
    dodela(0);
    t[0]=0;
    for(i=0;i<c;i++){
        segment tmp;
        tmp.l=0;
        tmp.v=0;
        for(j=0;j<4*v[i].size();j++) seg[i].push_back(tmp);
    }
    ojler(0);
    for(i=e.size()-1;i>=0;i--){
        p[e[i]]=i;
        spar[i][0]={a[e[i]].d,e[i]};
    }
    for(j=1;j<22;j++){
        for(i=0;i<e.size();i++){
            if(i+1<<j>e.size()) break;
            spar[i][j]=min(spar[i+(1<<(j-1))][j-1],spar[i][j-1]);
        }
    }
    cin>>m;
    for(i=0;i<m;i++){
        char o;
        cin>>o;
        cin>>x>>y;
        x--;
        y--;
        pom.a=x;
        pom.b=y;
        cin>>x;
        pom.v=x;
        u.push_back(pom);
    }
    sort(u.begin(),u.end(),poredi);
    for(i=0;i<m;i++){
        int l=lca(p[u[i].a],p[u[i].b]);
        upd(u[i].a,l,u[i].v);
        upd(u[i].b,l,u[i].v);
    }
    for(i=1;i<n;i++) cout<<i+1<<" "<<a[i].par+1<<" "<<query(a[i].c,1,0,v[a[i].c].size()-1,a[i].p)<<endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

minmaxtree.cpp: In function 'void dfs(int)':
minmaxtree.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dodela(int)':
minmaxtree.cpp:35:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
minmaxtree.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'std::vector<int> _merge(std::vector<int>, std::vector<int>)':
minmaxtree.cpp:52:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
       ~^~~~~~~~~
minmaxtree.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size() && j<b.size()){
                     ~^~~~~~~~~
minmaxtree.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(i<a.size()){ans.push_back(a[i]); i++;}
       ~^~~~~~~~~
minmaxtree.cpp:57:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while(j<b.size()){ans.push_back(b[j]); j++;}
       ~^~~~~~~~~
minmaxtree.cpp: In function 'void ojler(int)':
minmaxtree.cpp:95:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:154:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<4*v[i].size();j++) seg[i].push_back(tmp);
                 ~^~~~~~~~~~~~~~
minmaxtree.cpp:162:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<e.size();i++){
                 ~^~~~~~~~~
minmaxtree.cpp:163:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
             if(i+1<<j>e.size()) break;
                ~^~
minmaxtree.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i+1<<j>e.size()) break;
                ~~~~~~^~~~~~~~~
minmaxtree.cpp: In function 'void dodela(int)':
minmaxtree.cpp:42:24: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
 if(adj[n][i]==a[n].par || adj[n][i]==tmp) continue;

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42