제출 #72974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72974		yusufake	Min-max tree (BOI18_minmaxtree)	C++98	100 / 100	807 ms	61996 KiB

minmaxtree

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

#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define pp pair<int,int>

const int N = 7e4 + 4;
const int mod = 1e9 + 7;
vector < pp > V[N],A[N],B[N];
unordered_map < int , vector<pp> > M;
unordered_map < int , int > H,W;
int ans[N],U[N],sz[N],T[N],Mn[N],Mx[N],C;

void f(int x, int p, int n){
    int h=1; sz[x] = 1;
    for(auto y : V[x]){
        if(U[y.st] || y.st == p) continue;
        f(y.st,x,n);
        sz[x] += sz[y.st];
        if(sz[y.st] > n/2) h=0;
    }
    if(h && n-sz[x] <= n/2) C=x;
}
void g(int x, int p, int roo){
    T[x] = roo;
    for(auto y : V[x]){
        if(U[y.st] || y.st == p) continue;
        g(y.st,x,roo);
    }
}
pp h(int x, int p, int i){
    sz[x] = 1;
    int mn = 0;
    for(auto t : A[x]) if(T[t.st] && T[t.st] != T[x]) mn = max(mn , t.nd);
    int mx = mod;
    for(auto t : B[x]) if(T[t.st] && T[t.st] != T[x]) mx = min(mx , t.nd);
    pp a;
    for(auto y : V[x]){
        if(U[y.st] || y.st == p) continue;
        a = h(y.st,x,y.nd);
        mn = max(mn , a.st);
        mx = min(mx , a.nd);
        sz[x] += sz[y.st];
    }
    Mn[i] = max(Mn[i] , mn);
    Mx[i] = min(Mx[i] , mx);
    return mp(mn,mx);
}
void slv(int x, int n){
    f(x,-1,n);
    x = C;
    U[x] = 1;
    T[x] = -1;
    for(auto y : V[x]){
        if(U[y.st]) continue;
        g(y.st,x,y.st);
    }
    h(x,-1,0);
    g(x,-1,0);
    for(auto y : V[x]) if(!U[y.st]) slv(y.st,sz[y.st]);
}
void ff(int x){
    H[x] = 1;
    for(auto y : M[x]){
        if(H[y.st]) continue;
        ans[y.nd] = y.st;
        ff(y.st);
    }
}
void gg(int x, int p){
    H[x] = 1;
    for(auto y : M[x]){
        if(y.nd == p) continue;
        if(!H[y.st]) { ans[y.nd] = x; gg(y.st,y.nd); }
        else if(!ans[y.nd]) ans[y.nd] = x;
    }
}

int n,k,i,x,y,z,uu[N],vv[N],Z[N];
char c;
int main(){
    scanf("%d",&n);
    for(i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        V[x].pb(mp(y,i));
        V[y].pb(mp(x,i));
        Mx[i] = mod;
        uu[i] = x; vv[i] = y;
    }
    scanf("%d",&k);
    for(i=1;i<=k;i++){
        scanf(" %c%d%d%d",&c,&x,&y,&z);
        Z[i] = z;
        if(c == 'm') { A[x].pb(mp(y,z)); A[y].pb(mp(x,z)); }
        else { B[x].pb(mp(y,z)); B[y].pb(mp(x,z)); }
    }
    slv(1,n);

    for(i=1;i<n;i++)
        if(Mn[i] != 0 || Mx[i] != mod){
            M[ Mn[i] ].pb(mp(Mx[i],i));
            M[ Mx[i] ].pb(mp(Mn[i],i));
            W[ Mn[i] ]++; W[ Mx[i] ]++;
        }

    ff(0); ff(mod);
    for(i=1;i<=k;i++){
        x = Z[i];
        if(H[x]) continue;
        for(; W[x] == 1 ; x = z) {
            W[x]--;
            H[x] = 1;
            z = -1;
            for(auto y : M[x]){
                W[y.st]--;
                if(W[y.st] > 0){
                    ans[y.nd] = x;
                    z = y.st;
                }
            }
        }
    }
    for(i=1;i<=k;i++)
        if(!H[ Z[i] ])
            gg(Z[i],0);

    for(i=1;i<n;i++)
        printf("%d %d %d\n", uu[i], vv[i], ans[i] ? ans[i] : Mx[i]);
    return 0;
}

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

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
minmaxtree.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d%d%d",&c,&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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