QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88583#5502. Dazzling MountainJerryBlack#WA 796ms3912kbC++1710.5kb2023-03-16 16:46:442023-03-16 16:46:46

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-16 16:46:46]
  • 评测
  • 测评结果：WA
  • 用时：796ms
  • 内存：3912kb
查看
  • [2023-03-16 16:46:44]
  • 提交

answer

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

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")

#define DECIMAL 6
namespace fastIO
{
#ifdef LOCAL
#define DEBUG
#endif
#define BUF_SIZE 100000
#define LL long long
    static bool IOerror=false;
#ifdef DEBUG
    inline char nc(){char ch=getchar();if(ch==-1)IOerror=1;return ch;}
#else
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1){IOerror=true;return -1;}}return *p1++;}
#endif
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    template<class T> inline bool read(T&x){bool sign=false;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;if(ch=='-')sign=true,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;return true;}
    inline bool read(unsigned long long&x){char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return true;}
    inline bool read(unsigned int&x){char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return true;}
    inline bool read(double&x){bool sign=false;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return false;if(ch=='-')sign=true,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;return true;}
    inline bool read(char*s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return false;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;return true;}
    inline bool read(char&c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return false;}return true;}
    inline bool read(std::string&s){s.clear();char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return false;for(;!blank(ch)&&!IOerror;ch=nc())s+=ch;return true;}
    template<class T,class... U> bool read(T&h,U&... t){return read(h)&&read(t...);}
    struct Ostream_fwrite
    {
#ifdef DEBUG
        inline void out(char ch) { putchar(ch); }
#else
        char*buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
#endif
        template<class T> inline void print(T x){static char s[41],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(char ch){out(ch);}
        inline void print(unsigned long long x){static char s[41],*s1;s1=s;if(!x)*s1++='0';while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(unsigned int x){static char s[41],*s1;s1=s;if(!x)*s1++='0';while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void print(double x,int y=DECIMAL){static LL mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};if(x<-1e-12)out('-'),x=-x;x*=mul[y];LL x1=(LL)floor(x);if(x-floor(x)>=0.5)++x1;LL x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}}
        inline void print(char*s){while(*s)out(*s++);}
        inline void print(const char*s){while(*s)out(*s++);}
        inline void print(std::string s){print(s.c_str());}
#ifndef DEBUG
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
#endif // !DEBUG
    }Ostream;
    template<class T> inline void print(T x){Ostream.print(x);}
    template<class T> inline void println(T x){Ostream.print(x);Ostream.out('\n');}
    inline void print(double x,int y=DECIMAL){Ostream.print(x,y);}
    inline void println(double x,int y=DECIMAL){Ostream.print(x,y);Ostream.out('\n');}
    template<class T,class... U> void print(const T&h,const U&... t){print(h);Ostream.out(' ');print(t...);}
    template<class T,class... U> void println(const T&h,const U&... t){print(h);Ostream.out(' ');println(t...);}
#ifndef DEBUG
    inline void flush(){Ostream.flush();}
#endif
#undef LL
#undef DECIMAL
#undef BUF_SIZE
    //本地 getchar/putchar ，提交 fread/fwrite
    //本地支持终端交互输入输出
}
using namespace fastIO;

#define ll long long
#define ull unsigned ll
#define fi first
#define se second
const double eps=1e-9;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
mt19937 rnd(time(0));

int P=1e9+9;
namespace modint
{
    int norm(int x){if(x<0)x+=P;if(x>=P)x-=P;return x;}
    template<class T>
    T power(T a,ll n){T ans=1;while(n){if(n&1)ans=ans*a;a=a*a;n>>=1;}return ans;}
    struct Z
    {
        int x;
        Z(int x=0):x(norm(x)){}
        Z(ll x):x(norm(x%P)){}
        int val() const{return x;}
        Z operator-() const{return Z(norm(P-x));}
        Z inv() const{assert(x!=0);return power(*this,P-2);}
        Z&operator*=(const Z&rhs){x=(ll)x*rhs.x%P;return *this;}
        Z&operator+=(const Z&rhs){x=norm(x+rhs.x);return *this;}
        Z&operator-=(const Z&rhs){x=norm(x-rhs.x);return *this;}
        Z&operator/=(const Z&rhs){return *this*=rhs.inv();}
        friend Z operator*(const Z&lhs,const Z&rhs){Z res=lhs;res*=rhs;return res;}
        friend Z operator+(const Z&lhs,const Z&rhs){Z res=lhs;res+=rhs;return res;}
        friend Z operator-(const Z&lhs,const Z&rhs){Z res=lhs;res-=rhs;return res;}
        friend Z operator/(const Z&lhs,const Z&rhs){Z res=lhs;res/=rhs;return res;}
        friend istream&operator>>(istream&is,Z&a){ll v;is>>v;a=Z(v);return is;}
        friend ostream&operator<<(ostream&os,const Z&a){return os<<a.val();}
    };
}
using namespace modint;

#define int ll

struct node
{
    int id,siz;
    bool operator<(const node&n)const
    {
        return siz>n.siz;
    }
};

void solve()
{
    int n;
    cin>>n;
    vector<vector<int>>edge(n+1);
    vector<int>de(n+1),dd(n+1);
    vector<int>siz(n+1,1);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
        de[u]++;de[v]++;
        dd[u]++;dd[v]++;
    }
    vector<int>fa(n+1);
    function<void(int,int)>dfs=[&](int x,int f)
    {
        for(auto it:edge[x])if(it!=f)
        {
            fa[it]=x;
            dfs(it,x);
        }
    };
    dfs(1,0);
    priority_queue<node>q;
    vector<int>cnt(n+1);
    int num=0;
    for(int i=2;i<=n;i++)
    {
        if(de[i]==1)
        {
            q.push({i,siz[i]});
            cnt[1]++;
            num++;
        }
    }
    vector<int>ans;
    ans.push_back(1);
    int cntt=0;
    while(!q.empty())
    {
        auto [it,si]=q.top();
        q.pop();
        siz[fa[it]]+=si;
        cnt[si]--;
        num--;
        de[fa[it]]--;
        cntt++;
        if(de[fa[it]]==1)
        {
            q.push({fa[it],siz[fa[it]]});
            num++;
            cntt-=(dd[fa[it]]-1);
            cnt[siz[fa[it]]]++;
            if(cntt==0&&cnt[siz[fa[it]]]==num)ans.push_back(siz[fa[it]]);
        }
//        cout<<cntt<<'\n';
//        for(int i=1;i<=n;i++)cout<<cnt[i]<<" \n"[i==n];
    }
    ans.push_back(n);
    cout<<ans.size()<<'\n';
    for(auto it:ans)cout<<it<<' ';
    cout<<'\n';
}



#undef int

int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cout<<fixed<<setprecision(15);

	int _;cin>>_;while(_--)
    {
        solve();
    }
    return 0;
}
/* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S/L│P/B│ │Cal│   │   │   │
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┴───┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│  Enter │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │  Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│   Shift  │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│ Fn │Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3620kb

input:

1
9
1 2
2 3
3 4
3 5
2 6
6 7
7 8
7 9

output:

4
1 3 8 9

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 796ms
memory: 3912kb

input:

10000
906
675 189
555 889
491 97
791 419
175 694
713 842
788 513
159 354
670 815
652 546
253 87
89 278
563 429
522 900
202 657
331 865
35 605
735 532
612 471
657 386
7 886
856 164
224 777
73 534
481 631
711 698
240 465
115 181
191 825
311 155
709 501
207 849
294 546
591 682
96 405
210 696
861 13
781...

output:

63
1 3 4 34 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 
6
1 2 3 4 5 11 
28
1 2 3 4 5 6 15 16 17 18 19 20 21...

result:

wrong answer 41st lines differ - expected: '2', found: '3'
English 繁體中文 简体中文

Server Time: 2024-12-05 07:20:42 | OpenSource Project