oj.uz

Submission #64062

# Submission time Handle Problem Language Result Execution time Memory
64062 2018-08-03T09:36:14 Z Bodo171 Min-max tree (BOI18_minmaxtree) C++14
7 / 100
 1000 ms 11264 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=70005;
vector<int> v[nmax],ad[nmax];
pair<int,int> st[nmax],dr[nmax];
bool viz[nmax];
int l[nmax],r[nmax];
int tt[nmax],mark[nmax];
int n,m,i,j,L,val,a,b;
char ch;
bool changed=0;
void dfs(int x)
{
    for(int i=0;i<v[x].size();i++)
       if(!tt[v[x][i]])
    {
        tt[v[x][i]]=x;
        dfs(v[x][i]);
    }
}
int lca(int x,int y)
{
    int aux=x;
    while(x!=-1)
        mark[x]=1,x=tt[x];
    while(!mark[y])
        y=tt[y];
    while(aux!=-1)
        mark[aux]=0,aux=tt[aux];
    return y;
}
void set_mn(int x,int y)
{
    while(x!=L)
    {
        if(val>st[x].first)
            st[x]={val,i};
        x=tt[x];
    }
    while(y!=L)
    {
        if(val>st[y].first)
         st[y]={val,i};
         y=tt[y];
    }
}
void set_mx(int x,int y)
{
    while(x!=L)
    {
        if(val<dr[x].first)
            dr[x]={val,i};
        x=tt[x];
    }
    while(y!=L)
    {
        if(val<dr[y].first)
           dr[y]={val,i};
        y=tt[y];
    }
}
bool cup(int x)
{
    if(viz[x]) return 0;
    viz[x]=1;
    for(int i=0;i<ad[x].size();i++)
        if(!r[ad[x][i]])
    {
        l[x]=ad[x][i];
        r[ad[x][i]]=x;
        return 1;
    }
    for(int i=0;i<ad[x].size();i++)
        if(cup(r[ad[x][i]]))
    {
        l[x]=ad[x][i];
        r[ad[x][i]]=x;
        return 1;
    }
    return 0;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n-1;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    tt[1]=-1;
    dfs(1);
    for(i=1;i<=n;i++)
       st[i]={-1,0},dr[i]={(1<<30),0};
    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>ch>>a>>b>>val;
        L=lca(a,b);
        if(ch=='m') set_mn(a,b);
        else set_mx(a,b);
    }
    for(i=1;i<=n;i++)
    {
        if(st[i].second) ad[i].push_back(st[i].second);
        if(dr[i].second) ad[i].push_back(dr[i].second);
    }
    changed=1;
    while(changed)
    {
        changed=0;
        for(i=1;i<=n;i++)
            viz[i]=0;
        for(i=1;i<=n;i++)
            if((!l[i])&&cup(i))
              changed=1;
    }
    for(i=2;i<=n;i++)
    {
        if(!l[i])
        {
            if(st[i].second) val=st[i].first;
            if(dr[i].second) val=dr[i].first;
            cout<<i<<' '<<tt[i]<<' '<<val<<'\n';
        }
        else
        {
            if(l[i]==st[i].second) val=st[i].first;
            else val=dr[i].first;
            cout<<i<<' '<<tt[i]<<' '<<val<<'\n';
        }
    }
    return 0;
}

Compilation message

minmaxtree.cpp: In function 'void dfs(int)':
minmaxtree.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
minmaxtree.cpp: In function 'void set_mn(int, int)':
minmaxtree.cpp:44:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
         if(val>st[y].first)
         ^~
minmaxtree.cpp:46:10: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
          y=tt[y];
          ^
minmaxtree.cpp: In function 'bool cup(int)':
minmaxtree.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~
minmaxtree.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3704 KB Output is correct
2 Correct 5 ms 3816 KB Output is correct
3 Correct 6 ms 3816 KB Output is correct
4 Correct 5 ms 3816 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 8812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 11264 KB Output is correct
2 Correct 202 ms 11264 KB Output is correct
3 Execution timed out 1088 ms 11264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3704 KB Output is correct
2 Correct 5 ms 3816 KB Output is correct
3 Correct 6 ms 3816 KB Output is correct
4 Correct 5 ms 3816 KB Output is correct
5 Execution timed out 1085 ms 8812 KB Time limit exceeded
6 Halted 0 ms 0 KB -