QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345870 | #7860. Graph of Maximum Degree 3 | ushg8877 | WA | 42ms | 18672kb | C++14 | 2.7kb | 2024-03-07 16:30:35 | 2024-03-07 16:30:38 |
Judging History
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'