QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698313#8760. 不等式xingliu#WA 1ms3532kbC++203.1kb2024-11-01 18:49:282024-11-01 18:49:28

Judging History

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

  • [2024-11-01 18:49:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3532kb
  • [2024-11-01 18:49:28]
  • 提交

answer

/**
 *  author: xing huan liu kong 
 *  created: 2024-11-01 17:09:44
 *  
 *  即使这个图论(world)大的无边无际
 *  我也会深度优先搜索(dfs)找到你..
**/
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'  
#define point(x) fixed<<setprecision(x)
using namespace std;

#define int long long
typedef pair<int, int> PII;
typedef array<int, 3> arr;

void solve()
{
    int n, m; cin >> n >> m;

    vector<set<int>> e(n);
    vector<int> in(n, 0), put(n);

    for (int i = 0; i < m; i ++) {
        int x, y, z; cin >> x >> y >> z;
        x--, y--, z--;
        e[x].insert(y);
        e[x].insert(z);
    }

    for (int i = 0; i < n; i ++ ) {
        for (auto j : e[i]) {
            in[j] ++ ;
        }
    }

    vector<int> id = in;

    for (int i = 0; i < n; i ++ ) {
        put[i] = (int)e[i].size();
    }

    queue<int> q;
    vector<int> ans;
    
    for (int i = 0; i < n; i ++ ){
        if (!in[i]){
            q.push(i); // 先将 入度 为 0 的节点放入
        }
    }

    
    while (!q.empty()){
        
        int t = q.front();
        q.pop();
        ans.push_back(t);

        for (auto j : e[t]) {
            in[j] -- ;
            // cerr << j << " ";
            if (!in[j]) {
                q.push(j);
            }
        }
        // cerr << endl;
        
        // for (int i = 0; i < e[t].size(); i ++ ){
        //  	int j = e[t][i];
        //     in[j] -- ; // 入度 -- 
        //     if (!in[j]) { // 入度为 0 放入队列
        //         q.push(j);
        //     }
        // }
    }

    // for (int i = 0; i < n; i ++ ) {
    //     cerr << in[i] << " ";
    // }


    if (ans.size() != n) {
        cout << -1 << endl;
    } else {
        vector<int> cnt(n, 0);
        for (int i = 0; i < n; i ++ ) {
            if (!put[i]) cnt[i] = 1;
        }

        auto dfs = [&](auto &&self, int now) -> int {

            if (put[now] == 0) {
                return cnt[now];
            }

            // set<int> se;
            // for (auto &v : e[now]) {
            //     if (se.count(v)) continue;
            //     se.insert(v);
            //     cnt[now] += self(self, v);

            // }

            for (auto &v : e[now]) {
                cnt[now] += self(self, v);
                put[now] -- ;
            }


            return cnt[now];
        };

        for (int i = 0; i < n; i ++ ) {
            if (id[i] == 0) {
                dfs(dfs, i);
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] == 0) {
                for (auto &v : e[i]) {
                    cnt[i] += cnt[v];
                }
            }
            res += cnt[i];
            // cerr << cnt[i] << " ";
        }

        cout << (res <= 1e9 ? res : -1) << endl;
    }
}

signed main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int t = 1;

    while(t -- ){
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3532kb

input:

3 1
1 2 2

output:

3

result:

wrong answer 1st numbers differ - expected: '4', found: '3'