QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314910 | #7857. (-1,1)-Sumplete | one_god_and_two_dogs# | WA | 2ms | 20372kb | C++17 | 2.1kb | 2024-01-26 14:33:58 | 2024-01-26 14:33:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M=3e5+5;
int n,m,top;
int in[2][M];
vector<int>Q[2][M];
bool flag[M];
int stk[M];
int ans;
void dfs(int now) {
flag[now]=true;stk[++top]=now;
for(int i=0; i<Q[0][now].size(); ++i) {
int To=Q[0][now][i];
if(flag[To])continue;
dfs(To);
}
}
bool Check(int u,int v) {
for(int i=0; i<Q[1][u].size(); ++i) {
int To=Q[1][u][i];
if(To==v)return true;
}
return false;
}
void Solve_circle() {
stk[++top]=stk[1];
for(int i=1; i<top; ++i)
if(Check(stk[i],stk[i+1]))ans++;
}
void redfs(int now,int Fa) {
stk[++top]=now;
for(int i=0; i<Q[0][now].size(); ++i) {
int To=Q[0][now][i];
if(To==Fa)continue;
redfs(To,now);
}
}
void Solve_chain() {
int hd=0;
for(int i=1; i<=top; ++i)if(in[0][stk[i]]==1)hd=stk[i];
top=0;redfs(hd,0);
for(int i=1; i<top; ++i)
if(Check(stk[i],stk[i+1]))ans++;
if(top==2)return;
if(top==3){
if((Check(stk[1],stk[2])||Check(stk[3],stk[2]))&&Check(stk[1],stk[3]))ans++;
return ;
}
if(top>=4){
if(Check(stk[1],stk[2])&&Check(stk[3],stk[1]))ans++;
if(Check(stk[top],stk[top-1])&&Check(stk[top],stk[top-2]))ans++;
}
if(top>4)return;
if(Check(stk[1],stk[4])&&((Check(stk[1],stk[2])&&Check(stk[4],stk[3]))||
(Check(stk[1],stk[3])&&Check(stk[2],stk[4]))))ans++;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i) {
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
bool f=0;
for(int j=0; j<Q[c][u].size(); ++j)
if(Q[c][u][j]==v) {f=true;break;}
if(f)continue;
Q[c][u].push_back(v);++in[c][u];
Q[c][v].push_back(u);++in[c][v];
}
for(int i=1; i<=n; ++i) {
if(!flag[i]) {
top=0;
dfs(i);
if(top==1)continue;
int f=2;
for(int j=1; j<=top; ++j) {
if(in[0][stk[j]]==3) {f=3;break;}
if(in[0][stk[j]]==1) f=1;
}
if(f==3)continue;
if(f==2)Solve_circle();
if(f==1)Solve_chain();
}
}
ans+=n;
printf("%d",ans);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 20372kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
3
result:
wrong answer invalid output