QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201066#6354. 4ucup-team870WA 3ms19052kbC++141.8kb2023-10-05 09:34:072023-10-05 09:34:08

Judging History

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

  • [2023-10-05 09:34:08]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:19052kb
  • [2023-10-05 09:34:07]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 200010;

vector <int> e[N], ksj[N], g[N];
bitset<100010> bs[100010];
int eu[N], ev[N], du[N], vis[N];
P c[N];

bool cmp(P a, P b) {
    return a > b;
}

int main() {
    freopen("1.in", "r", stdin);
    int cc = clock();
    int n, m;
    scanf("%d%d", &n, &m);
    rep (i, 1, m) {
        scanf("%d%d", &eu[i], &ev[i]);
        du[eu[i]]++;
        du[ev[i]]++;
    }
    rep (i, 1, m) {
        int u = eu[i], v = ev[i];
        if (du[u] < du[v]) e[u].push_back(v), g[v].push_back(u);
        else if (du[u] > du[v]) e[v].push_back(u), g[u].push_back(v);
        else if (u < v) e[u].push_back(v), g[v].push_back(u);
    }

    rep (j, 1, m) {
        int u = eu[j], v = ev[j];
        for (auto x: e[u]) {
            vis[x] = 1;
        }
        for (auto x: e[v]) {
            if (vis[x]) {
                bs[x][j]=1;
            }
        }
        for (auto x: e[u]) {
            vis[x] = 0;
        }
    }
    ll ans = 0;

    // rep (i, 1, n) {
    //     c[i] = P(du[i], i);
    // }
    // sort(c+1, c+n+1, cmp);
    // rep (i, 1, n) {
    //     for (auto x: ksj[i]) {
    //         vis[x] = 1;
    //     }
    //     for (auto x: g[i]) {
    //         for (auto y: ksj[x]) {
    //             ans += vis[y];
    //         }
    //     }
    //     for (auto x: ksj[i]) {
    //         vis[x] = 0;
    //     }
    // }
    rep (j, 1, m) {
        int u = eu[j], v = ev[j];
        ans += (bs[u] & bs[v]).count();
    }
    cout << ans<<endl<<clock() - cc;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 19052kb

input:

5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5

output:

0
0

result:

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