现在的位置: 首页 > 综合 > 正文

hdu3290 The magic apple tree

2018年04月23日 ⁄ 综合 ⁄ 共 918字 ⁄ 字号 评论关闭

我晕,刚开始不知到怎么存数据,后来看了题解发现vector很神奇!

但是一看各位大神们都是用c++交的,G++交会TLE!最后自己套上输入外挂竟然AC了!才100ms+有木有!

太神奇了!这是我第一次用到输入外挂题目!

ps:以后我的代码风格使用松散加原味的代码,毕竟不能因为ACM而形成一股难以使用的代码习惯

code:

//从今天开始不再用宏定义
//采用松散的代码写法~~
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=20001;
vector<int> g[maxn];
int in[maxn], out[maxn];
int dfs(int root){
    if(out[root]==0)
        return root;
    vector<int> tmp;

    for(int i=0;i<out[root];i++)
        tmp.push_back(dfs(g[root][i]));

    sort(tmp.begin(),tmp.end());
    return tmp[(out[root]+1)/2-1];
}
char c;
inline void scan(int &x){
    while(c=getchar(),c<'0'||c>'9');
    x=c-'0';
    while(c=getchar(),c>='0'&&c<='9')x=x*10+c-'0';
}
int main()
{
    int N,tmp,i,j,root;
    while(~scanf("%d",&N))
    {
        for(i=1;i<=N;i++)
            g[i].clear();
        memset(in,0,sizeof(in));
        for(i=1;i<=N;i++)
        {
            scan(out[i]);
            for(j=1;j<=out[i];j++)
            {
                scan(tmp);
                g[i].push_back(tmp);
                in[tmp]++;
            }
        }
        for(i=1;i<=N;i++)
        {
            if(in[i]==0)
            {
                root=i;
                break;
            }
        }
        printf("%d\n",dfs(root));
    }
    return 0;
}

抱歉!评论已关闭.