QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290918#7854. 这不是一道数据结构题myee10 125ms56776kbC++117.3kb2023-12-25 20:48:202023-12-25 20:48:20

Judging History

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

  • [2023-12-25 20:48:20]
  • 评测
  • 测评结果:10
  • 用时:125ms
  • 内存:56776kb
  • [2023-12-25 20:48:20]
  • 提交

answer

// 那就是希望。
// 即便需要取模,也是光明。

#include <algorithm>
#include <set>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
    ullt v;
    inline ullt chg(ullt w){return(w<p)?w:w-p;}
    inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
    mod_ullt():v(0){}
    mod_ullt(ullt v):v(v%p){}
    inline bol empty(){return!v;}
    inline ullt val(){return v;}
    inline ullt&operator()(){return v;}
    inline friend bol operator==(mod_ullt a,mod_ullt b){return a()==b();}
    inline friend bol operator!=(mod_ullt a,mod_ullt b){return a()!=b();}
    inline mod_ullt operator+(){return*this;}
    inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a()+b());}
    inline mod_ullt&operator+=(mod_ullt b){return*this=*this+b;}
    inline mod_ullt operator-(){return _chg(p-v);}
    inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a+(-b);}
    inline mod_ullt&operator-=(mod_ullt b){return*this=*this-b;}
    inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a()*b();}
    inline mod_ullt&operator*=(mod_ullt b){return*this=*this*b;}
    inline friend mod_ullt operator/(mod_ullt a,mod_ullt b){return a*b.inv();}
    inline mod_ullt&operator/=(mod_ullt b){return*this=*this/b;}
    friend mod_ullt operator^(mod_ullt a,ullt b)
    {
        mod_ullt v(1);
        while(b)
        {
            if(b&1)v*=a;
            a*=a,b>>=1;
        }
        return v;
    }
    inline mod_ullt&operator^=(ullt b){return*this=*this^b;}
    inline mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
    inline mod_ullt&operator++(){return v=chg(v+1),*this;}
    inline mod_ullt operator--(int){mod_ullt ans=*this;return v=chg(v+p-1),ans;}
    inline mod_ullt&operator--(){return v=chg(v+p-1),*this;}
    inline mod_ullt inv(){return(*this)^(p-2);}
    mod_ullt sqrt()
    {
        if(((*this)^((p-1)>>1))!=1)return 0;
        mod_ullt b(1);do b++;while((b^((p-1)>>1))==1);
        ullt t=p-1;uint s=0;while(!(t&1))s++,t>>=1;
        mod_ullt x=(*this)^((t+1)>>1),e=(*this)^t,w=inv();
        for(uint k=1;k<s;k++,e=w*x*x)if((e^(1llu<<(s-k-1)))!=1)x*=b^((1llu<<(k-1))*t);
        ullt ans=x();_min(ans,p-ans);return ans;
    }
    voi read()
    {
        v=0;chr c;do c=getchar();while(c>'9'||c<'0');
        do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');
    }
    voi print(chr endc='\0')
    {
        static chr C[20];uint tp=0;
        ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
        while(tp--)putchar(C[tp]);
        if(endc)putchar(endc);
    }
    inline voi println(){print('\n');}
};
}
// Your shadow Gets in the way of my light
const ullt Mod=1e9+7;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
std::vector<uint>Way[200005],Son[200005],Ps[200005];
std::vector<std::pair<uint,uint> >Es[200005];uint tp;
voi dfs(uint p,uint f)
{
    static uint Dep[200005],S[200005],Dfn[200005],F[200005],cnt;
    static std::vector<uint>B;std::vector<uint>A;
    if(!~f)for(auto&s:Dfn)s=-1;
    F[p]=f,Dep[p]=B.size(),B.push_back(p),Dfn[p]=cnt++;
    for(auto s:Way[p])if(s!=f)
    {
        if(~Dfn[s])
        {
            if(Dep[s]<Dep[p])S[B[Dep[s]+1]]--,S[p]++;
        }
        else A.push_back(s),dfs(s,p),S[p]+=S[s];
    }
    B.pop_back(),Son[p]=A;
    if(!~f)while(A.size())
    {
        B={A.back()},A.pop_back(),Ps[tp]={F[B[0]]};
        while(B.size())
        {
            Ps[tp].push_back(p=B.back()),B.pop_back();
            for(auto s:Son[p])(S[s]?B:A).push_back(s);
        }
        static bol Now[200005];
        for(auto s:Ps[tp])Now[s]=true;
        for(auto s:Ps[tp])for(auto ss:Way[s])if(s<ss&&Now[ss])Es[tp].push_back({s,ss});
        for(auto s:Ps[tp])Now[s]=false;
        tp++;
    }
}
uint D[200005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n,m;scanf("%u%u",&n,&m);
    while(m--){uint u,v;scanf("%u%u",&u,&v);Way[--u].push_back(--v),Way[v].push_back(u);}
    dfs(0,-1);
    modint ans(n);
    while(tp--)
    {
        for(auto p:Ps[tp])D[p]++;
        if(Ps[tp].size()==2)continue;
        ans*=2;
        static uint Xor[400005],Deg[200005],cnt;
        static std::vector<uint>Eid[200005],Q;
        std::set<std::pair<uint,uint> >M;
        for(auto p:Ps[tp])Eid[p].clear();
        cnt=0;
        for(auto e:Es[tp])
            M.insert(e),Eid[e.first].push_back(cnt),Eid[e.second].push_back(cnt),Xor[cnt++]=e.first^e.second;
        for(auto p:Ps[tp])if((Deg[p]=Eid[p].size())==2)Q.push_back(p);
        while(Q.size())
        {
            uint p=Q.back(),u=-1,v=-1;Q.pop_back();if(Deg[p]!=2)continue;
            Deg[p]=0;for(auto e:Eid[p])if(~Xor[e])(~u?v:u)=p^Xor[e],Xor[e]=-1u;
            if(u>v)std::swap(u,v);
            if(M.count({u,v}))
            {
                if(--Deg[u]==2)Q.push_back(u);
                if(--Deg[v]==2)Q.push_back(v);
            }
            else M.insert({u,v}),Eid[u].push_back(cnt),Eid[v].push_back(cnt),Xor[cnt++]=u^v;
        }
        uint c=0;
        for(auto p:Ps[tp])if(Deg[p])c++;
        bol ok=c<=2;
        if(ok)
        {
            static uint F[200005];for(auto p:Ps[tp])F[p]=p,Deg[p]=0;
            auto find=[&](uint p)
            {
                while(p!=F[p])p=F[p]=F[F[p]];
                return p;
            };
            for(auto e:Es[tp])Deg[e.first]++,Deg[e.second]++;
            std::vector<std::pair<uint,uint> >QwQ;
            for(auto e:Es[tp])if(Deg[e.first]==2||Deg[e.second]==2)
                QwQ.push_back(e),F[find(e.first)]=find(e.second);
            for(auto e:Es[tp])if(find(e.first)!=find(e.second))
                QwQ.push_back(e);
            for(auto p:Ps[tp])Deg[p]=0;
            for(auto e:QwQ)Deg[e.first]++,Deg[e.second]++;
            ok&=QwQ.size()<=Ps[tp].size()&&QwQ.size()>=Ps[tp].size()-1;
            for(auto p:Ps[tp])ok&=Deg[p]>=1&&Deg[p]<=2;
            if(ok&&QwQ.size()==Ps[tp].size()-1)
            {
                uint u=-1,v=-1;
                for(auto p:Ps[tp])if(Deg[p]==1)(~u?v:u)=p;
                if(u>v)std::swap(u,v);
                ok=false;for(auto e:Es[tp])if(e==std::pair<uint,uint>{u,v})ok=true;
            }
        }
        if(!ok)return puts("0"),0;
    }
    for(uint i=0;i<n;i++)for(uint j=1;j<=D[i];j++)ans*=j;
    ans.println();
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 0ms
memory: 30436kb

input:

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

output:

56

result:

ok single line: '56'

Test #2:

score: 0
Accepted
time: 0ms
memory: 31256kb

input:

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

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 31208kb

input:

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

output:

0

result:

ok single line: '0'

Test #4:

score: -5
Wrong Answer
time: 0ms
memory: 30888kb

input:

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

output:

0

result:

wrong answer 1st lines differ - expected: '40', found: '0'

Subtask #2:

score: 5
Accepted

Test #5:

score: 5
Accepted
time: 116ms
memory: 49880kb

input:

200000 199999
76849 117660
190775 11517
36929 136177
161792 186900
165326 184615
74197 120051
7891 83240
121896 35204
83314 195652
104144 158348
71191 182187
122824 50031
108950 179173
165120 190230
156949 181392
171984 82834
96017 30143
58114 108979
38698 90371
185399 171751
139913 99465
71566 1324...

output:

437454115

result:

ok single line: '437454115'

Test #6:

score: 0
Accepted
time: 113ms
memory: 50796kb

input:

200000 199999
6574 23146
34257 69209
155380 164090
110026 127221
193115 99889
5635 174278
55712 77121
26697 49953
22754 96882
63538 126940
194879 165261
41026 41295
30210 92107
74413 48768
21400 93816
132836 161798
106855 181482
139713 172322
188984 22749
138035 187484
119125 94408
106547 197156
855...

output:

113291706

result:

ok single line: '113291706'

Test #7:

score: 0
Accepted
time: 110ms
memory: 50028kb

input:

200000 199999
31632 184606
168095 2953
125939 52574
192991 195231
89249 63587
67762 15189
127486 26911
55580 120635
164243 67832
132583 173571
144167 123204
145229 101807
103885 170616
134195 61189
192909 104601
164109 127893
96486 109669
155596 168629
144450 40523
111830 166912
21452 144116
168225 ...

output:

695768886

result:

ok single line: '695768886'

Test #8:

score: 0
Accepted
time: 106ms
memory: 50120kb

input:

200000 199999
163361 68930
19490 33356
160159 49369
191573 191277
25950 191040
87000 96084
87600 7514
36433 91932
124379 117605
192879 188658
132884 148743
167108 124881
145773 56391
131418 128073
157008 76084
141192 147983
85318 133420
94748 189411
50453 78717
71148 12192
164264 189793
112210 18103...

output:

733222740

result:

ok single line: '733222740'

Subtask #3:

score: 5
Accepted

Dependency #2:

100%
Accepted

Test #9:

score: 5
Accepted
time: 116ms
memory: 55888kb

input:

200000 200000
12724 99480
110070 33803
133108 189774
90549 132698
44107 190886
80834 45073
196688 3535
65325 152337
190962 142430
1881 60227
26322 185955
145062 99829
183113 179795
10631 100971
60798 37230
149752 51457
119906 123989
118777 44821
140764 181969
101534 197139
108651 135722
56961 189607...

output:

845696751

result:

ok single line: '845696751'

Test #10:

score: 0
Accepted
time: 107ms
memory: 56776kb

input:

200000 200000
101889 44867
88241 190435
89839 146284
5148 128828
32602 156348
31195 126576
146414 147950
70778 100220
13083 26015
6144 91822
141590 111136
44593 74957
138472 185562
75610 171998
48845 71030
175023 164685
128735 168341
15747 73835
169514 55205
119817 136636
190706 86265
148598 41994
1...

output:

654417965

result:

ok single line: '654417965'

Test #11:

score: 0
Accepted
time: 113ms
memory: 55052kb

input:

200000 200000
153577 8632
61036 84864
7655 90000
148729 89342
137385 7553
10222 50803
46720 102913
47837 105292
110223 81670
91157 108026
153903 139607
13230 84612
18282 113252
45158 195698
100923 170852
105927 41217
65631 826
105522 53451
173143 188641
176689 86349
150960 193904
15934 34208
72591 1...

output:

30336343

result:

ok single line: '30336343'

Test #12:

score: 0
Accepted
time: 125ms
memory: 55348kb

input:

200000 200000
139569 146207
179144 129709
26078 199032
175722 54209
174513 62650
157339 171357
119600 146013
50746 126175
183634 29260
30876 146213
53398 117000
115599 60981
90560 139790
2685 32865
53251 13733
60624 85594
41186 142244
157755 21032
167206 188574
161858 198651
157000 150869
113701 751...

output:

184856401

result:

ok single line: '184856401'

Subtask #4:

score: 0
Wrong Answer

Test #13:

score: 20
Accepted
time: 0ms
memory: 31120kb

input:

300 305
289 290
34 35
111 140
90 93
233 240
110 271
116 117
12 21
141 142
53 57
21 85
99 102
34 42
183 184
240 264
252 253
223 224
159 160
126 131
112 113
28 33
50 52
204 208
185 188
46 50
262 264
197 199
111 136
259 261
290 294
49 50
263 264
210 212
291 294
203 208
184 185
120 121
111 131
210 240
2...

output:

482487615

result:

ok single line: '482487615'

Test #14:

score: 0
Accepted
time: 3ms
memory: 30320kb

input:

300 320
233 237
208 217
90 92
277 278
226 246
79 80
37 40
1 9
190 191
213 214
94 96
231 232
162 163
9 10
226 227
172 173
168 169
131 135
158 159
133 134
59 60
61 102
52 57
161 180
172 174
84 86
207 208
54 55
9 16
118 119
122 123
166 170
212 215
38 39
264 266
180 196
65 69
287 288
22 23
24 28
201 202...

output:

821115099

result:

ok single line: '821115099'

Test #15:

score: -20
Wrong Answer
time: 0ms
memory: 31152kb

input:

300 350
104 106
257 259
216 298
250 251
147 148
217 218
220 267
284 285
249 250
232 233
145 209
257 258
283 287
232 238
255 256
206 207
189 190
23 25
48 51
75 115
187 193
14 18
90 94
81 82
45 48
90 91
42 44
51 54
154 155
174 175
60 62
82 85
99 100
160 161
216 217
200 202
226 231
255 257
252 253
36 3...

output:

0

result:

wrong answer 1st lines differ - expected: '427803536', found: '0'

Subtask #5:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 0ms
memory: 31188kb

input:

300 500
279 256
263 65
40 62
236 256
8 193
164 235
242 256
27 219
72 244
49 253
289 261
162 113
196 199
121 222
293 245
33 186
206 279
111 139
97 15
203 24
245 157
184 59
188 90
239 283
42 5
107 108
267 51
200 126
286 282
293 59
42 261
276 216
152 6
92 220
225 69
88 166
179 109
158 144
133 18
147 18...

output:

0

result:

wrong answer 1st lines differ - expected: '159215763', found: '0'

Subtask #6:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 3ms
memory: 31008kb

input:

300 597
181 11
16 186
144 42
80 274
72 186
238 172
7 268
225 118
198 84
274 214
170 27
181 44
171 74
270 266
20 6
296 108
45 25
32 198
99 86
129 110
281 273
67 47
259 107
277 265
264 145
215 218
264 164
156 281
100 23
284 125
109 280
92 203
108 74
227 171
213 81
262 239
206 111
5 23
90 121
77 274
23...

output:

0

result:

wrong answer 1st lines differ - expected: '600', found: '0'

Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%