Submission #258255

#	Time	Username	Problem	Language	Result	Execution time	Memory
258255		Mercenary	Duathlon (APIO18_duathlon)	C++14	100 / 100	216 ms	38988 KiB

count_triplets

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 4e5 + 6;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
int a[maxn];
int n , m;
vector<int> adj[maxn];
struct Tedge{
    int u , v;
    bool used;
}e[maxn];
int num[maxn] , low[maxn]  , dep[maxn];
int sz[maxn];
vector<int> adj1[maxn];
int id[maxn];
vector<int> st;
ll res = 0;

void DFS(int u , int par = 0)
{
    static int nTime = 0;
    static int biconnnect = 0;
    num[u] = low[u] = ++nTime;
    id[nTime] = u;st.pb(u);
    for(int c : adj[u])
    {
        if(e[c].used)continue;
        e[c].used = 1;
        int v = e[c].u + e[c].v - u;
        if(num[v] == 0){
            DFS(v ,u);
            if(low[v] >= num[u]){
                adj1[u].pb(n + ++biconnnect);
//                cout << u << " " << n + biconnnect << endl;
                while(true){
                    int tmp = st.back();st.pop_back();
//                    cout << n + biconnnect << " " << tmp << endl;
                    adj1[n + biconnnect].pb(tmp);
                    if(tmp == v)break;
                }
            }
            low[u] = min(low[u] , low[v]);
        }
        else{
            low[u] = min(low[u] , num[v]);
        }
    }
}
vector<int> now;
int cnt =  0;
void dfs(int u){
    sz[u] = (u <= n);
    if(u > n)now.pb(u);
    else cnt++;
    for(auto c : adj1[u]){
        dfs(c);
        if(u > n)res += 1ll * adj1[u].size() * sz[u] * sz[c];
        sz[u] += sz[c];
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m ; ++i)
    {
        cin >> e[i].u >> e[i].v;e[i].used = 0;
        adj[e[i].u].pb(i);
        adj[e[i].v].pb(i);
    }
    for(int i = 1 ; i <= n ; ++i){
        if(num[i] == 0){
            DFS(i);
            dfs(i);
            for(auto & u : now){
                res += 1ll * adj1[u].size() * sz[u] * (cnt - sz[u]);
            }
            res -= 1ll * cnt * (cnt - 1) / 2;
            now.clear();cnt = 0;
        }
    }
    cout << res * 2;
}

Compilation message (stderr)

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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