QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#314910#7857. (-1,1)-Sumpleteone_god_and_two_dogs#WA 2ms20372kbC++172.1kb2024-01-26 14:33:582024-01-26 14:33:59

Judging History

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

  • [2024-01-26 14:33:59]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:20372kb
  • [2024-01-26 14:33:58]
  • 提交

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