QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345870#7860. Graph of Maximum Degree 3ushg8877WA 42ms18672kbC++142.7kb2024-03-07 16:30:352024-03-07 16:30:38

Judging History

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

  • [2024-03-07 16:30:38]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:18672kb
  • [2024-03-07 16:30:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=1e5+5;
int n,m;ll ans=0;
vector<int> edg[MAXN][2],chn;
int p[MAXN],c[MAXN],tot,cnt;bool vis[MAXN];
struct node{int mn,cnt;};
node operator +(node x,node y){
	node z;
	z.mn=min(x.mn,y.mn);z.cnt=0;
	if(z.mn==x.mn) z.cnt+=x.cnt;
	if(z.mn==y.mn) z.cnt+=y.cnt;
	return z;
}
void operator +=(node &x,int y){
	x.mn+=y;
}
struct segt{
node val[MAXN<<2];int laz[MAXN<<2];
void build(int id=1,int l=0,int r=m-1){
	laz[id]=0;
	if(l==r) {val[id]=(node){l,1};return;}
	int mid=l+r>>1;
	build(id<<1,l,mid);build(id<<1|1,mid+1,r);
	val[id]=val[id<<1]+val[id<<1|1];
}
void pushdown(int id){
	laz[id<<1]+=laz[id],laz[id<<1|1]+=laz[id];
	val[id<<1]+=laz[id];val[id<<1|1]+=laz[id];
	laz[id]=0;
}
void add(int L,int R,int x,int id=1,int l=0,int r=m-1){
	if(L>R) return;
	if(L<=l&&r<=R){
		laz[id]+=x;val[id]+=x;
		return;
	}
	pushdown(id);
	int mid=l+r>>1;
	if(L<=mid) add(L,R,x,id<<1,l,mid);
	if(mid<R) add(L,R,x,id<<1|1,mid+1,r);
	val[id]=val[id<<1]+val[id<<1|1];
}
node ask(int L,int R,int id=1,int l=0,int r=m-1){
	if(L<=l&&r<=R) return val[id];
	pushdown(id);
	int mid=l+r>>1;
	if(R<=mid) return ask(L,R,id<<1,l,mid);
	if(mid<L) return ask(L,R,id<<1|1,mid+1,r);
	return ask(L,R,id<<1,l,mid)+ask(L,R,id<<1|1,mid+1,r);
}
}T;
void dfs(int u,int fa){
	p[u]=++tot;c[u]=cnt;
	for(int v:edg[u][0]) if(v!=fa){
		dfs(v,u);
	}
}
void dfs1(int u,int fa){
	chn.push_back(u);vis[u]=true;
	for(int v:edg[u][1]) if(v!=fa){
		dfs1(v,u);
	}
}
void solve(){
	static int stl[MAXN],str[MAXN],topl,topr,l;
	topl=topr=0;stl[0]=str[0]=-1;
	m=chn.size(),l=0;T.build();
	for(int i=0;i<m;i++){
		if(i!=0&&c[chn[i]]!=c[chn[i-1]]) l=i;
		int lst=i;
		while(topl&&p[chn[stl[topl]]]>p[chn[i]]){
			T.add(stl[topl-1]+1,lst-1,p[chn[stl[topl]]]-p[chn[i]]);
			lst=stl[topl-1]+1,topl--;
		}
		stl[++topl]=i;
		lst=i;
		while(topr&&p[chn[str[topr]]]<p[chn[i]]){
			T.add(str[topr-1]+1,lst-1,p[chn[i]]-p[chn[str[topr]]]);
			lst=str[topr-1]+1,topr--;
		}
		str[++topr]=i;
		ans+=T.ask(l,i).cnt;
	}
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,c;cin>>u>>v>>c;
		edg[u][c].push_back(v);
		edg[v][c].push_back(u);
	}
	for(int i=1;i<=n;i++) if(edg[i][0].empty()||edg[i][1].empty()){
		edg[i][0].clear();edg[i][1].clear();
	}
	for(int i=1;i<=n;i++) if(edg[i][0].size()<=1&&!p[i]) cnt++,dfs(i,0);
	for(int i=1;i<=n;i++) if(edg[i][1].size()<=1&&!vis[i]){
		chn.clear();dfs1(i,0);
		solve();
	}
	cout<<ans%998244353<<'\n';
	return 0;
}

详细

Test #1:

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

input:

3 4
1 2 0
1 3 1
2 3 0
2 3 1

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9812kb

input:

4 6
1 2 0
2 3 0
3 4 0
1 4 1
2 4 1
1 3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 1ms
memory: 10812kb

input:

20 28
9 6 1
9 6 0
3 8 0
8 4 0
3 8 1
3 4 1
2 13 0
13 1 0
19 1 0
2 1 1
2 19 1
13 19 1
14 15 1
14 15 0
7 12 0
12 17 0
20 17 0
7 17 1
7 20 1
12 20 1
16 18 0
18 10 0
5 10 0
16 10 1
16 5 1
18 5 1
4 6 0
9 11 0

output:

27

result:

ok 1 number(s): "27"

Test #4:

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

input:

100 150
93 23 0
23 81 0
76 81 0
93 81 1
93 76 1
23 76 1
100 65 0
65 56 0
19 56 0
100 56 1
100 19 1
65 19 1
2 98 0
2 98 1
26 63 0
63 90 0
26 63 1
26 90 1
6 11 0
11 67 0
6 11 1
6 67 1
37 89 0
89 64 0
25 64 0
37 64 1
37 25 1
89 25 1
84 10 0
10 29 0
75 29 0
84 29 1
84 75 1
10 75 1
7 70 1
7 70 0
28 92 0
...

output:

141

result:

ok 1 number(s): "141"

Test #5:

score: 0
Accepted
time: 35ms
memory: 18144kb

input:

100000 133680
36843 86625 0
86625 63051 0
35524 63051 0
36843 63051 1
36843 35524 1
86625 35524 1
55797 82715 0
55797 82715 1
70147 35104 0
35104 91732 0
70147 35104 1
70147 91732 1
94917 70395 0
70395 68250 0
24100 68250 0
94917 68250 1
94917 24100 1
70395 24100 1
83033 18450 1
83033 18450 0
34462 ...

output:

144604

result:

ok 1 number(s): "144604"

Test #6:

score: 0
Accepted
time: 39ms
memory: 17468kb

input:

100000 133388
86620 74346 0
74346 19047 0
54911 19047 0
86620 19047 1
86620 54911 1
74346 54911 1
23715 93094 0
93094 91208 0
63189 91208 0
23715 91208 1
23715 63189 1
93094 63189 1
99337 41426 1
99337 41426 0
83742 45546 0
45546 73862 0
83742 45546 1
83742 73862 1
85256 2812 0
2812 59368 0
85918 59...

output:

144348

result:

ok 1 number(s): "144348"

Test #7:

score: 0
Accepted
time: 42ms
memory: 18084kb

input:

100000 150000
86541 24385 0
24385 75745 0
52353 75745 0
86541 75745 1
86541 52353 1
24385 52353 1
89075 78015 0
89075 78015 1
52519 74846 0
74846 12045 0
73265 12045 0
52519 12045 1
52519 73265 1
74846 73265 1
17884 63159 0
63159 47308 0
56073 47308 0
17884 47308 1
17884 56073 1
63159 56073 1
72134 ...

output:

144639

result:

ok 1 number(s): "144639"

Test #8:

score: 0
Accepted
time: 42ms
memory: 18672kb

input:

100000 150000
91951 68612 1
91951 68612 0
18361 92673 0
92673 52678 0
86520 52678 0
18361 52678 1
18361 86520 1
92673 86520 1
58779 2421 0
58779 2421 1
66622 6461 0
6461 96943 0
66622 6461 1
66622 96943 1
27201 480 1
27201 480 0
19082 3895 0
3895 17796 0
3117 17796 0
19082 17796 1
19082 3117 1
3895 ...

output:

144471

result:

ok 1 number(s): "144471"

Test #9:

score: 0
Accepted
time: 42ms
memory: 18084kb

input:

100000 150000
43756 3552 0
3552 90269 0
43756 3552 1
43756 90269 1
11104 36935 1
11104 36935 0
11648 5480 0
5480 45320 0
11648 5480 1
11648 45320 1
19216 85746 0
19216 85746 1
68825 11173 0
11173 43155 0
68825 11173 1
68825 43155 1
27349 75259 0
27349 75259 1
1704 24478 0
24478 5980 0
1704 24478 1
1...

output:

144217

result:

ok 1 number(s): "144217"

Test #10:

score: 0
Accepted
time: 42ms
memory: 17524kb

input:

99999 149998
51151 43399 0
51151 43399 1
45978 28343 0
28343 9008 0
85724 9008 0
45978 9008 1
45978 85724 1
28343 85724 1
79446 12915 0
12915 65925 0
28869 65925 0
79446 65925 1
79446 28869 1
12915 28869 1
82642 95556 0
95556 68817 0
68334 68817 0
82642 68817 1
82642 68334 1
95556 68334 1
61212 7638...

output:

144219

result:

ok 1 number(s): "144219"

Test #11:

score: -100
Wrong Answer
time: 42ms
memory: 17512kb

input:

100000 149999
26736 28785 0
28785 37945 0
26736 28785 1
26736 37945 1
1240 74368 0
74368 45022 0
1240 74368 1
1240 45022 1
40673 1276 0
1276 56395 0
40673 1276 1
40673 56395 1
35181 63341 0
63341 35131 0
60120 35131 0
35181 35131 1
35181 60120 1
63341 60120 1
99363 36973 0
99363 36973 1
85717 77683 ...

output:

144378

result:

wrong answer 1st numbers differ - expected: '144380', found: '144378'