제출 #618077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618077		keta_tsimakuridze	철인 이종 경기 (APIO18_duathlon)	C++14	0 / 100	1095 ms	64956 KiB

count_triplets

#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int f[N], low[N], t[N], sz[2 * N], p[N], h[N];
ll bad = 0, s[2 * N];
int n;
vector<int> adj[2 * N];
vector<pii> V[N];
map<int,int> e[N];
int find(int u) {
    return (p[u] == u ? u : p[u] = find(p[u]));
}
void merge(int u, int v) {
    u = find(u), v = find(v);
    p[u] = v;
}
void dfs0(int u, int ID) {
    f[u] = 1;
    low[u] = h[u];
    for(int i = 0; i < V[u].size(); i++) {
        int v = V[u][i].f, id = V[u][i].s;
        if(ID == id) continue;
        if(f[v]) low[u] = min(low[u], h[v]);
        else    {
            t[id] = 1;
            h[v] = h[u] + 1;
            dfs0(v, id);
            if(low[v] < h[u]) merge(ID, id);
        }
    }
}
void dfs(int u, int p) {
    h[u] = h[p] + 1;
    sz[u] = 0;
    s[u] = 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if(v == p) continue;
        dfs(v, u);
        s[u] += s[v] + sz[u] * sz[v];
        sz[u] += sz[v];
    }
    if(h[u] % 2)s[u] += sz[u], sz[u]++;
    if(h[u] == 3) bad += s[u];
}
void ADD(int x, int y) {
    x += n;
    if(e[x][y]) return;
    e[x][y] = 1;
    adj[x].push_back(y);
    adj[y].push_back(x);
}
main() {
    int m;
    cin >> n >> m;
    vector<pair<int,int >> e;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back({v, i});
        V[v].push_back({u, i});
        e.push_back({u, v});
        p[i] = i;
    }
    dfs0(1, 0);
  //  for(int i = 1; i <= n; i++) V[i].clear();
    for(int i = 1; i <= m; i++) {
        if(!t[i]) continue;
        ADD(find(i), e[i - 1].f);
        ADD(find(i), e[i - 1].s);
    }
    for(int i = 1; i <= n; i++)
    dfs(i, 0);
    cout << (ll)n * (n - 1) * (n - 2) - 2 * bad;

}

컴파일 시 표준 에러 (stderr) 메시지

count_triplets.cpp: In function 'void dfs0(int, int)':
count_triplets.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs(int, int)':
count_triplets.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < adj[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
count_triplets.cpp: At global scope:
count_triplets.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10