QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#744193#4915. 海胆TheZone100 ✓4443ms201904kbC++208.2kb2024-11-13 21:06:572024-11-13 21:07:06

Judging History

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

  • [2024-11-13 21:07:06]
  • 评测
  • 测评结果：100
  • 用时：4443ms
  • 内存：201904kb
查看
  • [2024-11-13 21:06:57]
  • 提交

answer

#include<cstdio>
#include<vector>
using namespace std;
#define N 2005000
#define ll long long
int n,s[N][2],q,a,b;
ll as[N];
vector<pair<int,int> > qu[N];
struct segt{
	struct node{int l,r,lz,mn,ct,l1;ll s1;}e[N*2];
	void doit1(int x,int v){e[x].lz+=v;e[x].mn+=v;}
	void doit2(int x,ll v1){e[x].s1+=e[x].ct*v1;e[x].l1+=v1;}
	void pushdown(int x)
	{
		if(e[x].lz)doit1(x<<1,e[x].lz),doit1(x<<1|1,e[x].lz),e[x].lz=0;
		if(e[x].l1)
		{
			if(e[x<<1].mn==e[x].mn)doit2(x<<1,e[x].l1);
			if(e[x<<1|1].mn==e[x].mn)doit2(x<<1|1,e[x].l1);
			e[x].l1=0;
		}
	}
	void pushup(int x)
	{
		e[x].mn=min(e[x<<1].mn,e[x<<1|1].mn);
		e[x].ct=e[x<<1].ct*(e[x<<1].mn==e[x].mn)+e[x<<1|1].ct*(e[x<<1|1].mn==e[x].mn);
		e[x].s1=e[x<<1].s1+e[x<<1|1].s1;
	}
	void build(int x,int l,int r)
	{
		e[x].l=l;e[x].r=r;e[x].ct=r-l+1;e[x].mn=-1;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	}
	void modify1(int x,int l,int r,int v)
	{
		if(e[x].l>r||e[x].r<l)return;
		if(e[x].l>=l&&e[x].r<=r){doit1(x,v);return;}
		pushdown(x);
		modify1(x<<1,l,r,v);modify1(x<<1|1,l,r,v);
		pushup(x);
	}
	void modify2(int x,int l,int r)
	{
		if(e[x].l>r||e[x].r<l)return;
		if(e[x].l>=l&&e[x].r<=r){if(e[x].mn==0)doit2(x,1);return;}
		pushdown(x);
		modify2(x<<1,l,r);modify2(x<<1|1,l,r);
		pushup(x);
	}
	ll query(int x,int l,int r)
	{
		if(e[x].l>r||e[x].r<l)return 0;
		if(e[x].l>=l&&e[x].r<=r)return e[x].s1;
		pushdown(x);
		return query(x<<1,l,r)+query(x<<1|1,l,r);
	}
}tr;

int ch[N][2],fa[N],lz[N],mn[N],su[N],vi[N],st[N],cs;
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void doit(int x){ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];lz[x]^=1;}
void pushdown(int x){if(lz[x])doit(ch[x][0]),doit(ch[x][1]),lz[x]=0;}
void pushup(int x){mn[x]=min(mn[ch[x][0]],mn[ch[x][1]]);if(x>n)mn[x]=min(mn[x],x-n);su[x]=su[ch[x][0]]+su[ch[x][1]]+vi[x];}
void rotate(int x)
{
	int f=fa[x],g=fa[f],tp=ch[f][1]==x;
	if(nroot(f))ch[g][ch[g][1]==f]=x;fa[x]=g;
	ch[f][tp]=ch[x][!tp];fa[ch[x][!tp]]=f;
	ch[x][!tp]=f;fa[f]=x;
	pushup(f);pushup(x);
}
void splay(int x)
{
	st[cs=1]=x;
	while(nroot(st[cs]))st[cs+1]=fa[st[cs]],cs++;
	while(cs)pushdown(st[cs]),cs--;
	while(nroot(x))
	{
		int f=fa[x],g=fa[f];
		if(nroot(f))rotate((ch[g][1]==f)^(ch[f][1]==x)?x:f);
		rotate(x);
	}
}
void access(int x)
{
	int tp=0;
	while(x)
	{
		splay(x);
		ch[x][1]=tp;pushup(x);
		tp=x;x=fa[x];
	}
}
void makeroot(int x){access(x);splay(x);doit(x);}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y){split(x,y);splay(x);ch[x][1]=fa[y]=0;pushup(x);}
int di[N],cr,lb=1,f[N],ls[N],lc1,lc2;
int finds(int x){return f[x]==x?x:f[x]=finds(f[x]);}
void modify(int x,int v)
{
	access(x);splay(x);
	vi[x]=v;pushup(x);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&s[i][0],&s[i][1]);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)scanf("%d%d",&a,&b),qu[b].push_back(make_pair(a,i));
	for(int i=0;i<=n*2;i++)mn[i]=i>n?i-n:n+1;
	for(int i=1;i<=n;i++)f[i]=i;
	tr.build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		tr.modify1(1,ls[s[i][0]]+1,i,1);ls[s[i][0]]=i;
		tr.modify1(1,ls[s[i][1]]+1,i,1);ls[s[i][1]]=i;
		if(finds(s[i][0])==finds(s[i][1]))
		{
			split(s[i][0],s[i][1]);
			int ri=mn[s[i][1]];
			if(lc1<ri)lc2=lc1,lc1=ri;
			else if(lc2<ri)lc2=ri;
			cut(ri+n,s[ri][0]);cut(ri+n,s[ri][1]);
			tr.modify1(1,1,ri,1);
		}
		link(i+n,s[i][0]);
		link(i+n,s[i][1]);
		f[finds(s[i][0])]=finds(s[i][1]);
		tr.modify1(1,1,i,-1);
		di[s[i][0]]++;if(di[s[i][0]]==3)modify(s[i][0],1),cr++;
		di[s[i][1]]++;if(di[s[i][1]]==3)modify(s[i][1],1),cr++;
		while(lb<=lc1)
		{
			if(!lc1)break;
			split(s[lc1][0],s[lc1][1]);
			if(su[s[lc1][1]]==cr)break;
			di[s[lb][0]]--;if(di[s[lb][0]]==2)modify(s[lb][0],0),cr--;
			di[s[lb][1]]--;if(di[s[lb][1]]==2)modify(s[lb][1],0),cr--;
			lb++;
		}
		int li=max(lc2+1,lb),ri=lc1;
		if(ri&&li<=ri)tr.modify2(1,li,ri);
		for(int j=0;j<qu[i].size();j++)
		as[qu[i][j].second]=tr.query(1,qu[i][j].first,i);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",as[i]);
}
/*nswer

#include<cstdio>
#include<vector>
using namespace std;
#define N 2005000
#define ll long long
int n,s[N][2],q,a,b;
ll as[N];
vector<pair<int,int> > qu[N];
struct segt{
	struct node{int l,r,lz,mn,ct,l1;ll s1;}e[N*2];
	void doit1(int x,int v){e[x].lz+=v;e[x].mn+=v;}
	void doit2(int x,ll v1){e[x].s1+=e[x].ct*v1;e[x].l1+=v1;}
	void pushdown(int x)
	{
		if(e[x].lz)doit1(x<<1,e[x].lz),doit1(x<<1|1,e[x].lz),e[x].lz=0;
		if(e[x].l1)
		{
			if(e[x<<1].mn==e[x].mn)doit2(x<<1,e[x].l1);
			if(e[x<<1|1].mn==e[x].mn)doit2(x<<1|1,e[x].l1);
			e[x].l1=0;
		}
	}
	void pushup(int x)
	{
		e[x].mn=min(e[x<<1].mn,e[x<<1|1].mn);
		e[x].ct=e[x<<1].ct*(e[x<<1].mn==e[x].mn)+e[x<<1|1].ct*(e[x<<1|1].mn==e[x].mn);
		e[x].s1=e[x<<1].s1+e[x<<1|1].s1;
	}
	void build(int x,int l,int r)
	{
		e[x].l=l;e[x].r=r;e[x].ct=r-l+1;e[x].mn=-1;
		if(l==r)return;
		int mid=(l+r)>>1;
		build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	}
	void modify1(int x,int l,int r,int v)
	{
		if(e[x].l>r||e[x].r<l)return;
		if(e[x].l>=l&&e[x].r<=r){doit1(x,v);return;}
		pushdown(x);
		modify1(x<<1,l,r,v);modify1(x<<1|1,l,r,v);
		pushup(x);
	}
	void modify2(int x,int l,int r)
	{
		if(e[x].l>r||e[x].r<l)return;
		if(e[x].l>=l&&e[x].r<=r){if(e[x].mn==0)doit2(x,1);return;}
		pushdown(x);
		modify2(x<<1,l,r);modify2(x<<1|1,l,r);
		pushup(x);
	}
	ll query(int x,int l,int r)
	{
		if(e[x].l>r||e[x].r<l)return 0;
		if(e[x].l>=l&&e[x].r<=r)return e[x].s1;
		pushdown(x);
		return query(x<<1,l,r)+query(x<<1|1,l,r);
	}
}tr;

int ch[N][2],fa[N],lz[N],mn[N],su[N],vi[N],st[N],cs;
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void doit(int x){ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];lz[x]^=1;}
void pushdown(int x){if(lz[x])doit(ch[x][0]),doit(ch[x][1]),lz[x]=0;}
void pushup(int x){mn[x]=min(mn[ch[x][0]],mn[ch[x][1]]);if(x>n)mn[x]=min(mn[x],x-n);su[x]=su[ch[x][0]]+su[ch[x][1]]+vi[x];}
void rotate(int x)
{
	int f=fa[x],g=fa[f],tp=ch[f][1]==x;
	if(nroot(f))ch[g][ch[g][1]==f]=x;fa[x]=g;
	ch[f][tp]=ch[x][!tp];fa[ch[x][!tp]]=f;
	ch[x][!tp]=f;fa[f]=x;
	pushup(f);pushup(x);
}
void splay(int x)
{
	st[cs=1]=x;
	while(nroot(st[cs]))st[cs+1]=fa[st[cs]],cs++;
	while(cs)pushdown(st[cs]),cs--;
	while(nroot(x))
	{
		int f=fa[x],g=fa[f];
		if(nroot(f))rotate((ch[g][1]==f)^(ch[f][1]==x)?x:f);
		rotate(x);
	}
}
void access(int x)
{
	int tp=0;
	while(x)
	{
		splay(x);
		ch[x][1]=tp;pushup(x);
		tp=x;x=fa[x];
	}
}
void makeroot(int x){access(x);splay(x);doit(x);}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y){split(x,y);splay(x);ch[x][1]=fa[y]=0;pushup(x);}
int di[N],cr,lb=1,f[N],ls[N],lc1,lc2;
int finds(int x){return f[x]==x?x:f[x]=finds(f[x]);}
void modify(int x,int v)
{
	access(x);splay(x);
	vi[x]=v;pushup(x);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&s[i][0],&s[i][1]);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)scanf("%d%d",&a,&b),qu[b].push_back(make_pair(a,i));
	for(int i=0;i<=n*2;i++)mn[i]=i>n?i-n:n+1;
	for(int i=1;i<=n;i++)f[i]=i;
	tr.build(1,1,n);
	for(int i=1;i<=n;i++)
	{
		tr.modify1(1,ls[s[i][0]]+1,i,1);ls[s[i][0]]=i;
		tr.modify1(1,ls[s[i][1]]+1,i,1);ls[s[i][1]]=i;
		if(finds(s[i][0])==finds(s[i][1]))
		{
			split(s[i][0],s[i][1]);
			int ri=mn[s[i][1]];
			if(lc1<ri)lc2=lc1,lc1=ri;
			else if(lc2<ri)lc2=ri;
			cut(ri+n,s[ri][0]);cut(ri+n,s[ri][1]);
			tr.modify1(1,1,ri,1);
		}
		link(i+n,s[i][0]);
		link(i+n,s[i][1]);
		f[finds(s[i][0])]=finds(s[i][1]);
		tr.modify1(1,1,i,-1);
		di[s[i][0]]++;if(di[s[i][0]]==3)modify(s[i][0],1),cr++;
		di[s[i][1]]++;if(di[s[i][1]]==3)modify(s[i][1],1),cr++;
		while(lb<=lc1)
		{
			if(!lc1)break;
			split(s[lc1][0],s[lc1][1]);
			if(su[s[lc1][1]]==cr)break;
			di[s[lb][0]]--;if(di[s[lb][0]]==2)modify(s[lb][0],0),cr--;
			di[s[lb][1]]--;if(di[s[lb][1]]==2)modify(s[lb][1],0),cr--;
			lb++;
		}
		int li=max(lc2+1,lb),ri=lc1;
		if(ri&&li<=ri)tr.modify2(1,li,ri);
		for(int j=0;j<qu[i].size();j++)
		as[qu[i][j].second]=tr.query(1,qu[i][j].first,i);
	}
	for(int i=1;i<=q;i++)printf("%lld\n",as[i]);
}
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

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

output:

4
0
3
3
1

result:

ok 5 number(s): "4 0 3 3 1"

Test #2:

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

input:

97
4 1
1 2
6 7
1 3
7 6
3 1
4 5
1 2
3 5
3 2
29 2
31 94
8 80
32 8
46 8
8 31
31 29
32 29
12 32
2 1
1 3
7 2
6 8
3 2
3 2
3 4
5 1
2 3
3 2
4 1
4 8
5 3
1 2
2 1
4 9
1 3
2 4
6 5
62 9
7 27
27 64
88 27
88 64
27 9
6 9
2 3
8 5
5 7
8 4
5 4
1 2
3 2
10 5
2 1
1 2
2 5
2 1
2 1
5 3
9 2
1 3
3 2
1 3
3 5
3 4
2 4
4 6
3 1
2 ...

output:

87
0
10
19
9
1
47
1
12
16
0
64
13
15
54
54
40
4
0
52
35
35
15
0
4
68
61
31
63
35
13
29
44
21
27
2
13
50
0
48
35
73
1
42
35
42
68
48
8
3
44
40
27
52
54
24
3
0
20
21
14
35
2
9
22
70
5
39
16
0
55
43
14
22
20
47
55
48
22
31
25
4
42
0
26
21
51
42
35
27
24
34
44
8
51
36

result:

ok 96 numbers

Test #3:

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

input:

99
4 3
8 9
1 2
28 21
21 28
72 40
85 80
99 75
73 47
42 47
42 73
47 27
3 5
3 2
65 22
2 3
75 35
76 55
85 81
95 63
75 35
30 58
61 69
68 87
56 21
23 97
53 47
40 47
54 91
39 32
32 54
47 91
96 61
15 60
96 43
60 96
96 60
99 60
34 87
68 56
29 16
37 77
83 2
71 70
96 89
37 30
26 8
45 88
68 27
46 57
51 57
8 27
...

output:

19
4
2
3
13
8
5
13
0
4
2
13
19
0
4
8
5
6
1
2
3
3
15
3
15
2
2
7
0
11
0
5
4
16
2
11
12
0
15
15
11
0
8
10
2
2
4
2
5
7
8
3
3
0
12
14
11
11
6
2
14
5
0
1
12
8
2
0
8
4
11
4
14
5
13
11
7
2
14
2
4
14
5
6
12
3
3
1
14
2
8
12
0
5
13

result:

ok 95 numbers

Test #4:

score: 5
Accepted
time: 3ms
memory: 16092kb

input:

99
4 7
4 5
5 3
1 2
1 2
4 3
4 2
1 2
10 5
4 7
5 2
8 7
38 62
52 8
80 98
21 19
94 7
80 49
21 79
94 49
21 7
80 79
3 1
4 7
6 3
35 95
41 94
95 41
94 35
98 35
3 1
2 5
2 1
2 1
3 2
1 2
10 9
3 7
1 3
4 3
9 7
4 7
1 2
3 4
3 1
2 7
1 4
10 8
2 1
3 8
5 1
4 2
4 3
3 2
7 9
5 7
3 1
4 5
2 3
6 5
1 2
1 7
4 3
3 6
2 3
3 1
8 4...

output:

73
21
65
22
21
2
54
8
4
47
30
39
4
0
18
14
1
40
0
27
4
2
0
15
0
60
40
0
0
4
8
11
49
46
1
12
32
5
1
33
24
0
6
16
7
3
5
0
0
13
49
34
8
12
32
55
0
22
39
59
0
31
60
21
25
2
9
59
23
9
31
17
16
0
17
52
59
42
23
45
0
62
63
3
5
0
38
19
40
32
10
53
8
1
8
0
8
13

result:

ok 98 numbers

Test #5:

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

input:

100
5 6
3 5
1 6
1 4
6 5
9 6
2 4
7 2
1 2
78 17
68 78
68 17
16 17
5 1
2 3
4 1
98 54
97 20
62 98
81 62
20 95
95 81
97 98
2 1
2 7
8 5
3 6
5 1
2 7
8 7
2 6
4 8
1 3
1 3
2 1
4 1
1 2
87 29
51 38
87 51
51 87
28 87
71 12
71 12
3 1
1 2
2 4
2 4
3 1
38 59
15 38
15 74
74 59
81 59
2 6
9 5
94 65
59 14
59 18
18 65
14...

output:

68
36
18
30
43
17
2
33
13
16
33
0
8
24
37
19
21
0
2
49
0
24
42
23
36
28
0
56
13
30
0
29
19
5
0
20
3
12
9
4
38
30
38
40
9
0
6
25
33
19
26
4
38
37
21
12
48
17
40
6
12
2
33
22
28
53
63
28
0
36
26
19
25
3
64
13
2
0
2
28
2
17
11
2
34
30
29
40
4
14
22
38
5
26
52
22
2
42
42
15

result:

ok 100 numbers

Test #6:

score: 5
Accepted
time: 3ms
memory: 16092kb

input:

100
6 3
2 1
2 8
1 10
1 3
2 1
1 3
1 2
4 2
3 5
5 1
8 18
18 29
18 29
6 5
3 6
4 2
2 1
4 3
10 2
3 1
3 2
2 3
31 91
1 4
42 31
91 67
42 67
21 67
67 73
2 1
7 8
3 1
1 5
2 1
3 2
4 3
3 5
9 3
65 44
87 44
2 8
1 6
33 44
2 4
3 9
1 3
6 7
5 8
16 44
16 65
44 86
16 44
73 5
18 73
18 44
5 16
16 30
57 16
64 73
18 59
2 1
8...

output:

60
4
21
49
0
14
16
0
0
17
38
51
0
38
2
1
5
32
27
5
33
2
21
8
34
19
0
60
3
1
37
28
6
54
1
0
24
9
0
45
22
18
36
56
30
16
1
4
2
4
12
19
27
0
31
53
0
10
14
0
2
26
0
0
2
29
26
41
5
2
19
20
14
4
20
10
30
58
18
1
11
32
0
26
2
0
0
23
0
0
0
28
37
9
0
20
18
6
45
41

result:

ok 100 numbers

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 15
Accepted
time: 0ms
memory: 16136kb

input:

498
1 2
185 374
112 96
1 5
1 2
32 63
151 32
436 196
242 2
269 186
288 277
109 165
360 493
394 414
29 435
21 436
310 98
29 317
397 32
400 485
394 248
471 288
438 40
109 394
284 268
112 75
493 437
176 493
432 185
259 286
391 485
242 155
227 256
1 397
423 155
149 310
471 308
331 358
269 436
242 149
244...

output:

308
49
120
148
8
171
2
142
45
118
127
123
0
176
49
49
50
59
75
44
1
20
146
132
308
176
176
0
43
294
176
109
127
235
59
13
20
127
114
176
39
19
156
0
45
0
42
176
256
71
20
159
0
186
105
50
120
128
99
171
33
133
36
177
154
136
142
192
178
3
287
181
49
137
0
13
90
0
165
239
0
22
0
86
159
215
1
0
68
132...

result:

ok 498 numbers

Test #8:

score: 15
Accepted
time: 4ms
memory: 16188kb

input:

500
3 6
2 3
2 1
1 8
5 7
7 8
3 9
1 2
2 1
1 3
1 2
3 1
3 1
2 1
1 4
9 7
7 8
5 1
1 2
2 6
6 3
1 2
2 1
1 3
6 2
3 4
7 5
5 3
1 2
8 5
5 10
1 2
1 8
5 6
7 4
3 1
1 3
1 2
1 3
1 2
2 3
1 2
4 10
5 4
2 1
2 1
333 94
57 487
28 57
161 20
259 244
31 397
124 435
358 111
401 191
70 161
499 70
499 373
308 400
172 17
400 358...

output:

480
102
134
203
45
8
167
134
84
104
196
85
94
94
94
249
179
181
65
40
219
40
10
0
465
0
105
29
151
190
435
30
29
334
0
377
0
105
0
29
195
224
2
167
224
0
84
218
65
16
224
105
17
65
195
105
137
36
174
176
181
68
196
0
81
95
14
65
134
55
190
19
13
0
367
134
55
45
0
40
10
16
30
0
94
66
29
331
20
65
65
...

result:

ok 500 numbers

Test #9:

score: 15
Accepted
time: 5ms
memory: 16276kb

input:

500
3 5
387 191
212 238
449 389
58 137
58 137
418 214
315 412
455 204
232 36
3 238
140 242
242 140
484 304
164 314
35 121
464 79
257 492
451 185
22 288
209 383
3 455
295 314
499 397
393 418
205 127
58 418
23 418
455 263
110 335
314 18
464 368
397 299
58 356
464 121
85 58
451 391
397 129
397 314
451 ...

output:

319
185
74
26
50
118
127
92
26
54
50
92
82
93
177
94
24
0
63
95
3
24
221
129
128
0
180
50
50
0
0
145
0
246
0
121
0
0
93
143
220
121
157
0
59
97
50
23
249
95
23
0
47
24
119
124
218
50
1
21
79
3
30
128
50
86
27
24
249
142
69
30
84
94
41
122
108
0
97
48
15
180
92
47
26
1
29
143
180
26
95
29
1
25
24
24
...

result:

ok 500 numbers

Test #10:

score: 15
Accepted
time: 5ms
memory: 16260kb

input:

500
7 3
2 6
3 1
1 2
1 2
10 3
2 3
3 1
4 3
9 1
1 4
8 3
3 1
1 5
6 8
2 1
2 3
3 2
3 2
4 6
3 7
2 1
4 6
1 2
1 7
3 4
4 2
2 1
120 79
3 2
5 4
374 449
22 193
354 234
1 2
2 1
363 449
193 308
193 418
271 453
193 20
54 256
467 245
43 256
54 43
120 272
421 216
193 336
193 251
296 193
301 453
427 421
120 377
449 48...

output:

594
4
0
20
52
592
64
61
413
0
127
5
13
51
69
477
48
59
61
9
130
9
54
73
48
68
141
13
60
0
141
147
21
52
57
0
13
0
65
133
109
0
64
71
20
7
440
425
61
86
9
562
0
89
40
57
474
1
64
3
61
64
60
10
13
0
455
487
13
54
66
477
40
412
9
413
65
478
13
23
8
74
0
84
65
413
123
57
321
72
72
23
0
64
23
9
3
453
155...

result:

ok 500 numbers

Test #11:

score: 15
Accepted
time: 0ms
memory: 16256kb

input:

500
1 2
5 3
1 2
2 1
1 3
5 7
6 7
1 4
8 3
2 4
5 6
1 2
6 3
1 9
2 4
2 4
1 2
2 1
4 1
2 3
1 6
2 1
9 7
1 2
6 3
4 1
1 2
1 3
4 3
2 1
1 6
2 1
5 2
4 1
3 4
4 3
7 8
10 3
3 4
2 1
6 1
4 2
7 8
2 1
2 5
6 5
3 4
1 2
7 4
1 2
9 4
1 4
3 1
1 3
1 3
8 3
1 3
2 1
1 2
3 2
2 3
1 3
1 2
2 1
111 159
111 159
3 2
3 2
2 6
4 3
1 6
10 ...

output:

768
505
108
8
643
107
60
34
320
46
718
664
97
2
105
0
3
24
165
483
572
26
726
517
57
531
565
49
25
627
34
29
548
208
629
511
486
4
530
665
24
33
10
79
25
706
654
644
146
4
127
72
524
21
90
538
647
621
51
5
20
203
54
522
602
15
51
683
622
650
113
186
651
550
103
11
50
547
190
43
93
72
510
85
77
13
71...

result:

ok 500 numbers

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #12:

score: 15
Accepted
time: 13ms
memory: 18736kb

input:

4996
1 10
2 3
5 6
4 2
6 1
5 2
2 1
3 1
4 2
4 3
4 3
1 7
1 3
1 2
2 1
4 3
6 5
3 6
3 1
3 2
1 5
2 6
1 2
9 1
7 3
3 2
2 3
3 1
9 3
4 3
4 5
6 5
1 3
4 3
7 2
1 2
1 2
6 2
2 1
6 4
3 2
7 2
1 2
1 3
5 1
1 6
7 2
6 2
1 8
2 1
7 4
4 1
2 1
3 4
2 5
8 1
8 5
5 3
2 1
3 6
1 4
1 3
1 2
1 5
7 2
7 4
1 4
4 3
1 3
4 7
6 1
4 2
5 6
9 ...

output:

5990
188
3230
1916
0
189
3683
5361
5603
0
1915
930
188
5302
1916
1
2532
5475
1915
213
18
48
220
3481
1933
1891
0
1690
931
18
1934
170
1702
221
0
3682
214
5280
4
5412
1879
1916
5027
170
1933
1
4505
1003
1701
18
1
5545
2103
0
1916
1933
3326
188
2784
3485
0
2532
612
1698
1702
1934
18
0
1
1891
3522
0
21...

result:

ok 4996 numbers

Test #13:

score: 15
Accepted
time: 12ms
memory: 16536kb

input:

5000
6 7
4 10
2 3
3 2
2 1
1 3
4 5
1 2
4 2
1 2
1 2
2 3
2 9
4 1
1 2
2 1
5 1
3 6
1 3
1 3
2 3
3 2
5 4
1 5
2 1
2 3
1 8
1 2
2 4
1 2
6 9
1 3
3 2
2 3
8 2
5 2
2 3
2 1
4 1
146 4036
3203 2822
2892 694
1131 3233
3525 332
1221 756
1229 1536
2178 694
694 2350
2343 3589
1603 4810
2613 1336
4810 694
1336 964
2343 2...

output:

6803
177
2658
1812
557
5319
2745
795
4340
2516
5276
1780
126
1042
1123
1666
3697
1482
2625
4000
939
3205
5060
4398
1396
1229
2245
1381
3672
1806
2762
4291
491
1536
758
4
1297
1311
1238
3468
1703
672
2080
1229
2102
638
483
3257
3290
152
2435
4395
3604
1688
17
2035
529
2630
3070
2598
516
1138
3356
585...

result:

ok 5000 numbers

Test #14:

score: 15
Accepted
time: 8ms
memory: 16716kb

input:

5000
1 6
3 1
4 7
4 2
1 3
2 1
4 2
1 6
2 3
5 1
1 2
1 4
1 3
1 2
9 6
1 2
1 7
6 5
4 3
6 1
2 1
6 2
8 1
2 3
6 4
3 2
3 1
4 1
6 3
3 1
2 1
3 1
4 5
2 3
9 8
2 3
3 1
2 1
3 2
4 8
1 5
2 1
1 2
2 9
7 3
10 6
5 2
1 7
2 1
1 2
2 1
3 1
8 2
3 6
3 8
1 3
1 6
7 3
6 10
5 1
6 1
6 7
3 4
3 1
5 8
7 5
2 6
2 4
2 3
1 2
3 1
5 4
1 3
3...

output:

12605
9835
8732
5742
10572
31
914
879
1118
1092
11911
10888
7832
15
977
10837
9835
8735
11584
9473
0
561
6380
6864
1862
7986
9968
11168
6380
11230
9678
10691
413
992
9
1661
1136
2066
9835
1355
3775
10317
2010
10725
1299
1366
0
3833
3146
6879
11435
3
11617
10469
9832
11849
2041
11090
8732
4165
11259
...

result:

ok 5000 numbers

Test #15:

score: 15
Accepted
time: 12ms
memory: 16672kb

input:

5000
1 3
1 3
5 2
2 1
3 1
1 3
3 4
4 1
2 1
5 7
3 5
10 5
3 2
2 5
1 3
2 3
7 2
3 5
3 2
3 1
3 1
1 3
3 5
1 5
2 4
3 2
3 1
3 6
1 3
1 2
2 1
2 1
1 2
7 4
3 2
8 4
1 8
1 2
3 5
4 3
2 1
5 1
3 1
5 3
1 2
2 1
7 4
3 5
1 2
1 2
5 4
3 5
1 3
1 3
2 3
3 4
5 7
5 3
5 6
6 5
7 2
2 6
1 3
5 1
2169 2173
3017 3079
3431 2217
2029 221...

output:

9253
1207
5979
844
7864
1678
5183
5565
2115
5531
1124
4383
5771
5458
1661
1
1164
2056
1220
2544
565
7704
2256
5105
9075
3327
613
2380
3328
64
1807
1630
222
6579
4560
5391
848
3627
690
868
7425
512
0
2420
1
3083
2502
2368
4972
5699
4255
668
13
4360
811
7262
443
6919
6166
223
5508
4590
4867
1365
5582
...

result:

ok 5000 numbers

Test #16:

score: 15
Accepted
time: 8ms
memory: 16660kb

input:

5000
1 6
6 8
1 3
3 7
5 7
1 2
1 5
2 8
7 5
7 3
2 4
6 2
1 2
5 3
1 2
10 6
2 3
5 2
8 1
6 1
1 7
1 5
2 4
3 2
6 1
2 4
2 7
1 2
2 1
2 5
1 2
1 6
2 1
2 3
5 1
3 7
5 2
9 4
4 5
1698 2236
2166 3865
2236 2166
1526 1530
2166 1439
10 6
5 6
2 1
8 6
1530 1439
1439 4499
1439 2166
2 6
4 1
2 1
4 2
1 5
2 7
4 8
3 7
2 1
6 2
1...

output:

31787
14922
0
15031
28287
28459
27154
27082
362
275
8292
224
673
206
27679
27755
31139
15862
27358
0
27082
4507
27637
0
3301
388
31102
28115
27358
30
27082
3073
27637
12899
27366
27999
118
27639
137
601
30632
276
14250
29067
0
27639
673
16535
7458
179
31245
27785
26
31314
7
27358
0
23002
477
616
276...

result:

ok 5000 numbers

Subtask #4:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #17:

score: 15
Accepted
time: 99ms
memory: 29132kb

input:

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

output:

60000
26923
28354
17155
40133
31923
43127
7928
47066
3635
463
7456
5576
3632
2450
42642
301
23261
14424
12169
19848
1754
10509
27037
16843
9877
12621
8980
14833
186
2922
8726
7078
33377
20304
30278
16385
36956
30881
8472
27786
18608
16056
16701
5444
35616
26112
18246
41122
25299
23090
29792
28830
31...

result:

ok 50000 numbers

Test #18:

score: 15
Accepted
time: 86ms
memory: 26588kb

input:

49999
1 2
1 2
2 1
3 1
5 6
1 3
8 4
3 1
1 6
2 1
2 1
10 2
2 3
2 1
3 5
1 2
5 6
3 4
7 6
4 3
6 7
4 1
2 3
7 2
5 2
8 7
2 3
1 2
4 3
5 1
7 2
1 2
6 4
3 2
6 1
3 1
3 4
6 3
6 1
3 6
1 3
6 3
1 2
5 3
3 1
1 2
1 3
2 1
4 2
1 2
5 7
1 3
1 3
2 1
1 8
2 3
1 3
1 7
1 5
5 2
1 3
4 2
9 8
3 1
6 5
5 6
2 3
1 3
3 1
4 3
1 2
2 1
7 1
2...

output:

275937
237662
6643
82
266693
250205
221014
6144
22015
29245
2463
241142
262488
699
253306
20482
1463
21146
21347
266789
2933
14665
14157
226993
245656
12959
260207
243637
9643
230967
247631
1535
265005
2957
2385
246162
238096
247074
192442
4176
268404
231484
25479
32421
244399
259415
124552
251385
2...

result:

ok 49995 numbers

Test #19:

score: 15
Accepted
time: 93ms
memory: 26996kb

input:

50000
5 4
2 3
10 2
8 6
2 5
2 1
7 6
6 2
5 2
6 4
4 1
4 8
2 1
2 4
8 1
3 4
3 1
5 4
7 2
1 2
4 5
8 9
6 2
3 1
1 2
2 1
1 2
2 1
5 1
1 3
5 3
6 7
1 7
2 1
1 3
4 3
2 8
1 2
4 7
1 2
1 3
2 1
4 7
2 5
7 3
10 4
3 6
2 4
2 6
4 1
4 2
4 6
2 5
2 1
2 5
5 3
5 4
6 7
2 1
3 2
2 1
10 7
2 1
6 4
3 2
1 2
1 2
1 3
2 3
3 1
6 5
2 1
3 6...

output:

169213
120366
76907
32378
7198
86993
61596
80803
38569
75542
36937
14528
115397
77020
37755
79637
145452
3613
82267
96362
64481
47922
54959
52825
12360
72937
93542
26569
102097
96296
79162
855
78073
10019
15141
2770
59873
114110
86624
37344
42028
16224
140031
37635
39580
10943
110851
146778
128030
1...

result:

ok 50000 numbers

Test #20:

score: 15
Accepted
time: 99ms
memory: 26628kb

input:

49997
2 10
1 3
4 1
5 2
8 5
7 2
3 1
2 5
1 4
3 1
48597 7937
14962 3483
48818 47114
34306 1793
1 6
8 2
6 3
8 2
8 2
7 6
1 6
3 1
9331 47946
48818 36815
7937 40900
40138 23406
16468 9709
9400 30978
11754 48597
48818 21416
47946 38519
47946 21416
9400 1812
1793 9400
40138 30663
11643 16468
11754 23513
2234...

output:

157269
33653
23819
76455
118476
44543
59046
49422
28610
17548
65694
39585
16855
16067
28735
49686
149418
83164
58263
29198
109035
5047
48160
38826
127708
34779
20530
68913
76799
31109
114263
85023
86767
44417
66800
15486
102030
88200
21214
22070
40559
59311
17401
3957
78119
97658
72965
20499
16132
5...

result:

ok 49998 numbers

Test #21:

score: 15
Accepted
time: 90ms
memory: 26916kb

input:

50000
3 6
6 1
5 2
1 2
2 4
6 1
5 4
2 6
4 5
5 1
5 4
4 7
3 5
2 1
5 1
8 3
1 10
3 2
6 4
3 1
3 5
3 2
1 2
1 6
2 3
8 4
2 3
2 1
2 3
6 2
6 5
2 1
1 2
2 5
3 2
7 2
5 2
8 9
4 2
5 3
3 1
1 3
6 2
7 4
3 2
6 3
2 1
7 3
2 1
5 6
2 3
5 4
1 3
1 2
6 7
2 3
2 1
8 4
1 2
1 6
1 7
3 1
3 1
5 6
1 3
8 3
7 3
2 3
7 6
5 6
2 1
3 1
1 2
3...

output:

162140
42246
96814
25397
33104
47007
29382
77557
3269
53838
10943
5831
101194
131296
34710
45033
61613
68985
69533
79053
28544
35179
121526
15199
6224
73763
28819
48551
58273
48436
21773
96820
12508
28490
25110
3535
126369
113968
28886
36446
84547
95587
14431
7643
71545
13732
44292
28572
42936
20078...

result:

ok 50000 numbers

Subtask #5:

score: 15
Accepted

Test #22:

score: 15
Accepted
time: 1874ms
memory: 150172kb

input:

1000000
1 2
1 4
2 1
3 6
6 5
1 3
10 5
2 4
9 6
3 2
1 2
5 1
4 3
1 3
1 4
2 9
6 4
1 2
1 2
1 2
3 4
3 4
7 5
1 2
1 2
2 1
7 8
1 2
5 4
1 3
2 1
4 2
1 4
1 4
4 2
1 3
1 3
7 4
3 4
3 2
2 1
1 2
1 2
2 5
10 6
2 3
2 5
7 2
5 4
4 5
5 7
2 1
8 5
2 1
2 1
1 3
4 6
3 1
2 5
4 8
6 3
1 4
1 2
1 3
9 8
6 5
3 4
3 2
1 3
4 2
1 6
2 1
1 ...

output:

11235160

result:

ok 1 number(s): "11235160"

Test #23:

score: 15
Accepted
time: 3016ms
memory: 149716kb

input:

1000000
1 2
8 2
8 6
4 8
6 10
2 7
2 1
3 1
2 3
9 1
6 4
2 1
5 3
1 2
3 5
2 4
3 2
3 1
4 2
7 4
3 9
3 2
2 1
1 6
5 1
3 2
1 2
8 3
4 2
2 1
5 6
1 2
2 1
3 1
7 1
2 3
4 5
1 4
5 6
4 1
9 7
3 2
1 5
2 5
2 1
1 2
5 7
5 3
5 4
4 3
1 2
4 1
1 4
9 8
6 4
1 5
10 3
7 6
6 1
3 2
2 1
3 2
5 3
2 5
2 3
4 3
1 7
5 2
3 4
2 4
3 2
6 2
4 ...

output:

1273941717

result:

ok 1 number(s): "1273941717"

Test #24:

score: 15
Accepted
time: 2844ms
memory: 147868kb

input:

1000000
2 7
5 4
1 2
3 4
4 6
1 3
2 5
4 5
8 2
5 2
4 1
8 7
5 6
5 4
3 4
2 4
1 2
1 2
2 3
5 3
3 4
3 1
1 9
2 1
2 1
2 1
1 2
8 4
8 6
7 8
4 2
6 5
3 1
8 3
1 2
5 3
5 1
4 2
4 2
2 1
2 4
2 4
3 2
2 1
3 4
4 5
9 4
2 9
2 5
7 3
5 7
4 1
4 3
8 7
3 5
5 1
1 2
6 5
2 4
2 3
5 6
7 1
2 4
8 9
5 2
1 2
1 4
3 8
2 6
1 5
6 4
4 2
10 2...

output:

293147241

result:

ok 1 number(s): "293147241"

Test #25:

score: 15
Accepted
time: 2761ms
memory: 150652kb

input:

1000000
3 5
3 4
3 4
7 2
5 6
1 8
3 4
8 9
8 3
2 4
4 6
1 2
6 3
3 6
1 3
2 8
3 4
3 2
3 1
4 2
6 8
5 2
2 4
7 6
1 2
5 1
3 1
2 3
8 7
2 5
5 7
1 4
6 4
2 1
1 4
2 10
4 1
6 3
10 1
1 6
1 2
6 2
1 2
2 1
4 3
2 1
6 5
7 4
3 2
3 4
4 2
1 3
1 4
6 5
2 1
3 5
1 3
3 2
4 3
8 10
5 4
2 4
7 1
9 7
1 3
6 3
3 1
2 6
3 1
5 6
8 10
1 3
...

output:

6429173

result:

ok 1 number(s): "6429173"

Test #26:

score: 15
Accepted
time: 1847ms
memory: 149520kb

input:

1000000
1 2
5 6
4 5
1 2
4 2
6 5
1 2
4 1
1 2
3 7
1 4
4 2
8 6
8 7
5 1
2 1
6 8
5 8
3 1
7 2
5 4
3 2
3 7
3 5
5 1
6 3
3 2
4 3
2 5
5 8
1 2
8 5
4 6
2 7
2 1
2 5
1 2
2 8
1 10
3 2
2 1
1 4
3 10
5 1
2 6
2 1
5 1
1 4
10 6
2 5
2 1
3 1
5 6
3 2
3 4
3 5
2 5
10 7
4 2
1 2
1 2
4 2
6 4
3 2
1 6
2 1
7 2
6 1
3 5
3 2
5 8
5 3
...

output:

11021330

result:

ok 1 number(s): "11021330"

Subtask #6:

score: 15
Accepted

Test #27:

score: 15
Accepted
time: 2992ms
memory: 200712kb

input:

1000000
194603 719066
675018 226509
79442 45350
917512 353429
61308 216895
411878 891116
152492 299355
285259 500703
362450 305858
809620 298590
353068 307896
594296 243696
962716 546635
865529 461074
454115 255260
569303 319052
266164 139614
575510 107514
840723 802795
583117 41941
891173 661899
94...

output:

9091998699
0
0
0
0
0
346906248
0
0
1143585630
0
0
0
0
0
0
7428392628
0
0
8972723033
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6621121160
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8151167...

result:

ok 1000000 numbers

Test #28:

score: 15
Accepted
time: 3011ms
memory: 200952kb

input:

999999
277180 856839
588071 449201
51753 908421
359383 46415
61069 109604
549825 622887
720143 466065
390245 206365
807513 20517
878566 378167
235285 133115
380785 668163
490900 851251
523551 284335
604873 703765
60692 740539
857768 96880
477134 359425
255375 109515
16280 822745
938032 600291
468767...

output:

33635277939
0
0
0
0
10528386041
0
0
0
0
0
0
0
0
0
11094604056
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
24270166500
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
797044144
1196152272
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 999998 numbers

Test #29:

score: 15
Accepted
time: 2885ms
memory: 200480kb

input:

999995
626695 185616
639165 587565
269075 528124
208827 585290
712290 614274
422688 886801
907253 827210
283937 124067
131608 374181
183405 110647
999951 88542
331056 221068
1058 854385
510581 422551
52500 786849
930677 776215
958140 568204
940869 866106
570266 324470
842441 258797
938934 309290
534...

output:

646563058
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
328398470
0
328288380
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
446617750
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
530949306
0
0
0
0
0
0
...

result:

ok 999998 numbers

Test #30:

score: 15
Accepted
time: 3015ms
memory: 198140kb

input:

1000000
890120 116113
613346 383997
946766 416560
38259 928163
10212 108304
847 126212
878208 297665
259312 998196
973715 533692
91989 730452
960890 170500
833652 57544
572161 679957
115287 222647
766331 209018
224824 929920
646533 939676
94851 886064
872075 642142
992730 574504
661755 671756
207548...

output:

9988759013
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2844763450
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2603932108
0
0
1857829450
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4660...

result:

ok 1000000 numbers

Test #31:

score: 15
Accepted
time: 2931ms
memory: 199956kb

input:

1000000
991775 273562
318336 354051
94745 567598
90609 481136
5634 20624
139950 390735
772730 163368
896033 229957
738466 236885
284178 26383
484600 843894
260433 661955
951062 166397
657942 974840
91309 868826
747814 574110
264079 496652
823741 820186
428060 110016
183494 812752
713620 172806
36854...

output:

625748170
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
388115662
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
380851493
0
0
0
0
0
0
276629100
0
0
0
0
0
0
0
0
0
0
0
213441800
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
498572994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
530285029
0
0
0
41778479...

result:

ok 1000000 numbers

Subtask #7:

score: 20
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #32:

score: 20
Accepted
time: 3459ms
memory: 200952kb

input:

1000000
4 5
2 8
4 3
6 7
4 1
4 9
1 2
1 9
3 5
7 9
5 4
2 3
1 3
4 3
8 1
10 4
2 1
2 1
2 5
2 1
4 3
5 7
5 4
1 2
1 7
3 4
1 3
5 4
5 7
4 2
7 2
1 2
5 9
2 8
3 2
8 2
2 4
7 2
1 2
3 2
1 9
6 2
4 1
2 8
2 6
2 3
2 3
1 2
3 4
1 10
2 1
8 3
10 2
9 3
2 1
2 9
3 6
3 7
1 9
1 2
2 3
2 6
1 2
2 1
6 4
1 3
4 3
2 1
1 9
1 10
1 2
2 1
...

output:

980650431
289713
25544617
221785419
935638893
24266886
4867016
951433616
955693245
24311
21051318
3504248
3706708
2477923
491140
41700401
24604585
2390113
491132
662521098
2389090
27700037
21140223
40644340
22747325
22686827
31250486
1056347
18448653
0
6648719
15824247
20560178
24818559
22833016
352...

result:

ok 1000000 numbers

Test #33:

score: 20
Accepted
time: 3809ms
memory: 200544kb

input:

999995
2 1
7 8
7 3
3 1
1 3
2 1
8 10
2 4
2 1
2 1
7 4
5 1
4 2
2 1
5 1
3 5
2 1
3 8
5 7
2 1
5 3
6 5
2 1
1 9
3 7
3 4
1 2
2 1
1 2
2 6
5 7
2 1
1 3
1 3
3 5
1 4
5 8
3 2
3 9
3 1
4 3
5 6
2 6
1 4
8 1
5 2
6 1
5 2
1 2
7 3
1 2
3 6
2 3
3 1
3 2
1 2
2 4
1 2
5 3
1 2
3 1
2 4
3 4
1 3
7 1
7 1
3 1
3 1
8 6
1 4
5 7
6 1
1 2
...

output:

31711149
867015
190047
0
136372
29408084
136372
8657616
14086
8657345
615520
29709394
29231434
22691973
479452
3120
1604013
29690590
20791
156500
29704844
8657519
615824
0
29690590
663
20791
0
168921
21895354
7805210
29710718
29847264
21465875
31317494
6705
21945023
1624384
0
29711381
21053939
29704...

result:

ok 999996 numbers

Test #34:

score: 20
Accepted
time: 3953ms
memory: 201140kb

input:

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

output:

170600610
141
3047836
87218
169594594
170503127
1124423
166546794
169566736
167379439
170427190
167379439
166518919
143789824
0
105726876
170430007
130007
63116855
167379439
167379439
1056279
34780
166518968
1239435
0
929668
166546843
867103
162029375
0
133701
832596
263952
3075111
3047766
167379439...

result:

ok 1000000 numbers

Test #35:

score: 20
Accepted
time: 3778ms
memory: 199936kb

input:

999995
7 8
4 1
1 4
5 7
4 1
4 1
2 4
3 2
3 8
8 7
5 2
4 2
2 8
5 1
1 2
1 4
3 2
5 2
3 4
2 7
2 1
2 1
6 1
2 1
4 5
2 1
2 3
2 3
2 3
6 7
1 4
3 1
5 3
1 2
7 6
2 1
5 1
1 3
2 1
5 2
3 2
4 2
1 2
1 2
2 4
1 5
1 4
3 1
3 1
7 6
2 1
5 3
4 3
10 5
6 3
6 3
5 2
1 3
3 4
2 4
1 2
1 2
4 1
4 2
2 1
1 6
5 2
3 1
5 2
7 9
3 8
2 1
3 7
...

output:

114279896
6983926
106399351
69724579
7734345
8620742
214294
15614565
106405633
85781962
6079606
3462261
86272544
8620742
96981538
98004209
74480238
640846
7023454
8418933
38057923
15547248
86930
1448475
6477859
29759
4997201
0
30621
3221
58968219
9411649
6353964
6435272
6253641
3691
24204596
3803719...

result:

ok 999996 numbers

Test #36:

score: 20
Accepted
time: 4443ms
memory: 197248kb

input:

1000000
1 3
1 4
7 8
1 4
4 8
1 2
3 5
2 6
1 4
2 3
2 7
2 1
1 2
1 6
4 5
5 7
1 5
4 2
10 9
2 6
2 6
2 5
2 5
3 4
1 10
6 4
5 1
4 1
6 2
2 1
1 6
1 6
6 8
2 5
5 1
3 9
2 1
1 2
5 10
1 2
5 2
1 2
5 1
8 2
4 2
5 3
1 2
4 1
1 3
1 5
3 4
2 1
5 1
5 3
2 1
3 6
1 3
1 2
2 7
8 5
4 2
5 2
2 10
4 5
2 1
1 3
1 2
2 1
1 5
7 3
3 4
5 2
...

output:

419197178
0
0
1109607
1068964
0
417693156
508844
6710551
417092393
18232825
409866736
0
1337
5634577
758627
7825081
6480390
6710549
452846
1109607
16365009
10407746
17451206
13379
230159
6262
6716811
400218958
399460943
7826420
0
416358231
1346028
508844
417693156
0
7826420
1109607
1339
16886797
0
0...

result:

ok 1000000 numbers

Test #37:

score: 20
Accepted
time: 4214ms
memory: 201904kb

input:

1000000
2 1
4 2
9 3
4 9
5 1
8 7
5 6
1 3
6 5
2 3
4 2
7 3
4 1
5 3
6 10
6 4
4 1
1 3
3 4
7 6
1 2
4 2
1 2
3 2
5 3
4 6
4 5
2 1
1 2
4 5
7 1
1 5
2 1
4 6
6 5
5 3
3 1
4 3
4 2
2 3
3 10
2 6
1 6
3 4
1 2
3 1
8 4
5 1
7 4
2 4
3 1
4 8
7 1
2 10
5 6
3 2
3 4
1 2
1 2
2 1
6 2
1 2
8 1
8 9
1 2
2 1
1 2
7 5
1 3
8 3
1 6
2 1
2...

output:

168905715
0
206463
30081620
6148992
14381623
122120748
142196132
22379
142651513
6377794
5886069
136075402
63803
6580920
0
137022465
6380992
434243
136066795
153730695
156914667
136297666
30092072
6167347
33973
5863093
20550395
5886731
30068325
142767360
142180317
434243
6113522
467059
142273453
142...

result:

ok 1000000 numbers

Test #38:

score: 20
Accepted
time: 2942ms
memory: 201748kb

input:

1000000
6 1
1 4
1 10
8 9
2 3
6 9
1 9
2 6
4 6
3 1
1 3
6 2
5 7
2 4
3 2
4 6
8 1
3 5
1 4
855567 14619
216304 891101
684049 622662
527154 946519
164579 212008
268938 212008
550279 996616
962869 827422
196684 101725
693667 103162
917556 647010
969384 773362
353321 103999
828507 948517
270741 278451
1 3
25...

output:

10137526
3842760
439752
2464689
7120852
4886034
5673833
5012658
5171442
7696720
8265315
143857
3253147
1484523
7126739
5865114
631500
3743278
3338861
3275050
6665656
3448568
2654424
6733213
312138
2839183
595473
592760
1992576
3641908
412209
4243669
1364759
873658
1205795
418419
5697974
1116500
2004...

result:

ok 1000000 numbers

Test #39:

score: 20
Accepted
time: 2930ms
memory: 200808kb

input:

999996
3 2
3 2
2 4
3 1
1 2
5 1
6 1
5 7
2 1
2 3
6 2
3 1
5 3
1 5
3 1
5 7
4 6
8 4
7 5
3 1
3 7
2 1
2 1
4 3
3 2
7 4
2 1
2 4
2 1
1 7
3 1
2 5
10 1
5 2
1 4
3 2
1 2
4 3
2 3
4 2
8 4
6 4
1 3
3 4
7 6
2 3
3 1
2 10
3 6
1 3
4 7
4 1
8 9
2 6
3 2
2 6
1 3
3 4
6 1
3 1
6 7
1 2
1 2
1 2
1 2
4 1
6 4
3 6
1 2
1 6
2 1
4 5
9 2...

output:

10500120
1363375
731330
4068884
7144505
5798264
8257789
3028231
4449494
5286198
858430
2201722
4583158
7316428
777157
6816870
7180341
1366182
1736303
100044
1678615
3510294
1682449
6671608
2026526
4468007
2106119
1039608
241373
2694375
3596411
6778523
5379989
1312500
6190592
2752306
6921031
1208476
...

result:

ok 999998 numbers

Test #40:

score: 20
Accepted
time: 4260ms
memory: 200436kb

input:

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

output:

307474493
4673137
271651346
305510938
271651346
30189931
30189931
21012339
488138
272910955
5635196
30196659
272410174
302606801
271492980
251409851
0
277080669
1406022
551
2322
305509941
251368126
20149273
272412517
45548004
272412955
251397835
300842193
66894
21002674
920416
559
272409708
466
3018...

result:

ok 999996 numbers

Test #41:

score: 20
Accepted
time: 3028ms
memory: 200744kb

input:

1000000
1 2
4 3
7 9
3 1
6 9
3 1
2 3
1 4
4 3
2 7
8 5
2 3
9 4
1 7
1 5
1 2
7 3
2 9
2 1
7 6
2 1
3 2
7 9
2 1
9 4
2 4
1 2
1 3
2 3
2 1
1 2
3 1
1 5
7 2
2 4
5 1
1 4
2 1
5 6
4 2
4 1
3 1
2 4
3 1
3 1
3 4
3 8
1 2
8 2
1 2
3 6
2 1
2 5
4 5
4 3
4 5
4 2
1 2
2 1
6 8
10 1
3 2
2 4
5 4
2 1
5 3
6 8
7 6
2 4
2 1
10 5
1 2
3 ...

output:

10202555
2247171
6554005
1929753
8665623
5432741
2433487
1168607
3246643
2460156
4567381
2811212
1073686
1285152
6585501
722340
2508669
835198
5701388
2153805
1800201
1486884
1733194
3323068
4353964
2205923
5302115
7499409
1613661
5288527
7486883
5134062
1352887
719761
2100145
6286572
6734880
593320...

result:

ok 1000000 numbers
English 繁體中文 简体中文

Server Time: 2024-12-02 10:14:59 | OpenSource Project