QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#698252#8760. 不等式xingliu#WA 0ms3880kbC++202.4kb2024-11-01 18:23:082024-11-01 18:23:15

Judging History

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

  • [2024-11-01 18:23:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2024-11-01 18:23:08]
  • 提交

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<vector<int>> e(n);
    vector<int> in(n);
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z;
        x--, y--, z--;
        e[x].push_back(y);
        e[x].push_back(z);
        in[y]++;
        in[z]++;
    }

    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 (int i = 0; i < e[t].size(); i ++ ){
         	int j = e[t][i];
            in[j] -- ; // 入度 -- 
            if (!in[j]) { // 入度为 0 放入队列
                q.push(j);
            }
        }
    }

    if (ans.size() != n) {
        cout << -1 << endl;
    } else {
        int st = -1;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                st = i;
                break;
            }
        }
        vector<int> cnt(n);
        auto dfs = [&](auto &&self, int now) -> int {
            if (cnt[now]) return cnt[now];
            set<int> se;
            for (auto &v : e[now]) {
                if (se.count(v)) continue;
                se.insert(v);
                cnt[now] += self(self, v);
            }
            if (cnt[now] == 0) return cnt[now] = 1;
            return cnt[now];
        };

        dfs(dfs, st);

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

input:

3 1
1 2 2

output:

2

result:

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