QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627043#7860. Graph of Maximum Degree 3LeoTeng#WA 3ms12044kbC++142.2kb2024-10-10 14:34:182024-10-10 14:34:20

Judging History

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

  • [2024-10-10 14:34:20]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:12044kb
  • [2024-10-10 14:34:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b) ; ++i)
#define all(x) begin(x) , end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int , int> pii;
typedef vector<int> vi;
const int MAXN = 2e5+5;
int deg[2][MAXN],ded[MAXN];
vector<pii>adj[MAXN];
int par[2][MAXN],szz[2][MAXN];
int find(int x,int c){
    if(par[c][x] == x)return x;
    return par[c][x] = find(par[c][x],c);
}
void unite(int a,int b,int c){
    a = find(a,c);
    b = find(b,c);
    if(a==b)return;
    par[c][a] = b;
    szz[c][b] += szz[c][a];
}
map<pii,int>mp[2];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n,m;
    cin>>n>>m;
    ll ans = n;
    for(int i=1;i<=n;i++){
        par[0][i] = par[1][i] = i;
        szz[0][i] = szz[1][i] = 1;
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a>b)swap(a,b);
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
        deg[c][a]++;
        deg[c][b]++;
        mp[c][{a,b}]++;
    }
    for(auto [x,y]:mp[0]){
        if(mp[1][x])ans++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(!deg[0][i] || !deg[1][i]){
            q.push(i);
            ded[i] = 1;
        }
    }
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto [x,c]:adj[v]){
            if(!ded[x])continue;
            deg[c][x]--;
            if(!deg[c][x]){
                ded[x] = 1;
                q.push(x);
            }
        }
    }

    vector<vector<int>>comp(n+1);
    for(int i=1;i<=n;i++){
        if(ded[i])continue;
        int v = i;
        for(auto [x,c]:adj[v]){
            if(ded[x] || c)continue;
            unite(v,x,c);
        }
    }
    for(int i=1;i<=n;i++){
        if(ded[i])continue;
        comp[find(i,0)].push_back(i);

    }
    for(int i=1;i<=n;i++){
        if(szz[0][find(i,0)] <=2 )continue;
        set<int>s;
        for(int v:comp[i]){
            for(auto [x,c]:adj[v]){
                if(ded[x])continue;
                unite(v,x,c);
            }
        }
        for(int v:comp[i])s.insert(find(v,1));
        ans += sz(s) == 1;

    }


    cout<<ans<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11800kb

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: 0ms
memory: 12044kb

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: -100
Wrong Answer
time: 3ms
memory: 11804kb

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:

26

result:

wrong answer 1st numbers differ - expected: '27', found: '26'