oj.uz

Submission #133509

# Submission time Handle Problem Language Result Execution time Memory
133509 2019-07-21T01:57:16 Z 12tqian Duathlon (APIO18_duathlon) C++14
0 / 100
 1000 ms 88796 KB 
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>


using namespace std;


const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e5 + 5;
vi adj[MAX];
vi comp[MAX];
vi bcomp[MAX];
ll precomp[MAX];
int bad[MAX];
unordered_map<int, int> node;
unordered_map<int, int> sub;
unordered_map<int, int> parent;
unordered_map<int, vi> tree;
int dfs(int src, int par){
   // cout <<" here" << endl;
    assert(src>=0);
    parent[src] = par;
    sub[src] = sz(bcomp[src]);
    if(src>=MAX){
        sub[src] = sz(bcomp[src - MAX]) - bad[src-MAX];
    }
    else{
        sub[src] = 1;
    }
    node[src] = sub[src];
    for(int nxt: tree[src]){
        if(nxt != par){
            sub[src] += dfs(nxt, src);
        }
    }
    return sub[src];
}
template<int SZ> struct BCC {
    int N;
    vi adj[SZ];
    vector<vpi> fin;

    void addEdge(int u, int v) { adj[u].pb(v), adj[v].pb(u); }

    int ti = 0, disc[SZ], low[SZ], comp[SZ], par[SZ];
    vpi st;

    void BCCutil(int u, bool root = 0) {
        disc[u] = low[u] = ti++;
        int child = 0;

        trav(i,adj[u]) if (i != par[u])
            if (disc[i] == -1) {
                child ++; par[i] = u;
                st.pb({u,i});
                BCCutil(i);
                low[u] = min(low[u],low[i]);

                // disc[u] < low[i]: bridge
                if ((root && child > 1) || (!root && disc[u] <= low[i])) { // articulation point!
                    vpi tmp;
                    while (st.back() != mp(u,i)) tmp.pb(st.back()), st.pop_back();
                    tmp.pb(st.back()), st.pop_back();
                    fin.pb(tmp);
                }
            } else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
                st.pb({u,i});
            }
    }

    void bcc(int _N) {
        N = _N;
        f1r(i,1,N+1) par[i] = disc[i] = low[i] = -1;
        f1r(i,1,N+1) if (disc[i] == -1) {
            BCCutil(i,1);
            if (sz(st)) fin.pb(st);
            st.clear();
        }
    }
};
BCC<MAX> bcc;
bool contains(int i, int x){
    int l = 0;
    int r = sz(bcomp[i]) - 1;
    while(l<= r){
        int m = (l+r)/2;
        if(bcomp[i][m] == x) return true;
        else if(bcomp[i][m]<x) l = m+1;
        else r = m-1;
    }
    return false;
}
int n;
int get(int above, int below){
    if(parent[below] == above){
        return sub[below];
    }
    else{
        return n - sub[above];
    }
}
int main(){
    fast_io();
    int m;
    cin >> n >> m;
    f0r(i, m){
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].eb(v);
        adj[v].eb(u);
        bcc.addEdge(u+1, v+1);
    }
    bcc.bcc(n);
    int sz = sz(bcc.fin);
    f0r(i, sz){
        for(auto e: bcc.fin[i]){
            comp[e.f-1].eb(i);
            comp[e.s-1].eb(i);
            bcomp[i].eb(e.f-1);
            bcomp[i].eb(e.s-1);
        }
    }
    f0r(i, n){
        set<int> s (all(comp[i]));
        comp[i].assign(all(s));
    }
    f0r(i, sz){
        set<int> s (all(bcomp[i]));
        bcomp[i].assign(all(s));
    }
    /*f0r(i, sz){
        cout << i<< " bcomp: ";
        for(int x: bcomp[i]) cout << x << " ";
        cout << endl;
    }*/
    f0r(i, n){
        if(sz(comp[i]) == 1)continue;
        for(int c: comp[i]){
            tree[i].eb(c+MAX);
            tree[c+MAX].eb(i);
        }
    }
    /*for(auto x: tree){
        if(x.f>=MAX){
            cout << x.f-MAX<< " comp: ";
        }
        else cout << x.f << " : ";
        for(int y: x.s){
            if(y>= MAX){
                cout << y-MAX <<"b ";
            }
            else cout<<y << " ";
        }
        cout << endl;

    }*/

    f0r(i,sz){
        for(int x: bcomp[i]){
            if(sz(comp[x]) >1){
                bad[i]++;
            }
        }
    }

    /*f0r(i, sz){
        cout << i << " sz: " << bad[i] << endl;
    }
    cout << endl;*/
    dfs(MAX, -1);
    f0r(i, sz){
        for(int x: bcomp[i]){
            if(sz(comp[x]) > 1){
                ll val = get(i+MAX, x);
                precomp[i] += (val)*(val-1);
            }
        }
    }
    /*for(auto x: sub){
        if(x.f>= MAX){
            cout << x.f-MAX <<" comp: ";
        }
        else cout << x.f << " : ";
        cout <<x.s << endl;
    }*/
   // return 0;
    ll ans = 0;
    f0r(i, n){
        if(sz(comp[i]) == 1){
            ///not a cut point
            ll cur = n-1;
            cur *=(cur-1);
            int c = comp[i][0];
            for(auto pnt: bcomp[c]){
                if(sz(comp[pnt]) > 1){///cut point
                    ll val = get(c+MAX, pnt);
                    cur -= val*(val-1);
                    //if(i == 0) cout << c << " " << pnt << " " << get(c+MAX, pnt) << " adfasdf" << endl;
                }
            }
           // cout << i << " df " << cur << endl;
            ans += cur;
        }
        else{
            ll cur = n-1;
            cur *= (cur-1);
            for(int nxt: tree[i]){
                ll val = precomp[nxt-MAX];
                ll subtract = get(nxt, i);
                val -= subtract*(subtract - 1);
               // if(i == 6) cout << nxt-MAX << " asdfasdf " << val << endl;
                cur -= val;
            }
            //cout << i << " " << cur << endl;
            ans += cur;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

count_triplets.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
count_triplets.cpp: In member function 'void BCC<SZ>::BCCutil(int, bool)':
count_triplets.cpp:92:27: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
         trav(i,adj[u]) if (i != par[u])
                           ^
count_triplets.cpp: In function 'void io(std::__cxx11::string)':
count_triplets.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 37228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10360 KB Output is correct
2 Correct 14 ms 10328 KB Output is correct
3 Correct 14 ms 10232 KB Output is correct
4 Correct 15 ms 10568 KB Output is correct
5 Correct 15 ms 10488 KB Output is correct
6 Correct 15 ms 10488 KB Output is correct
7 Correct 15 ms 10616 KB Output is correct
8 Correct 15 ms 10436 KB Output is correct
9 Correct 14 ms 10460 KB Output is correct
10 Incorrect 13 ms 10232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 64496 KB Output is correct
2 Correct 559 ms 64528 KB Output is correct
3 Correct 564 ms 64544 KB Output is correct
4 Correct 544 ms 64720 KB Output is correct
5 Correct 535 ms 64628 KB Output is correct
6 Correct 689 ms 88796 KB Output is correct
7 Correct 651 ms 74332 KB Output is correct
8 Correct 631 ms 72164 KB Output is correct
9 Correct 595 ms 70076 KB Output is correct
10 Incorrect 528 ms 58760 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 10360 KB Output is correct
2 Correct 14 ms 10360 KB Output is correct
3 Correct 14 ms 10232 KB Output is correct
4 Correct 14 ms 10232 KB Output is correct
5 Correct 13 ms 10104 KB Output is correct
6 Correct 13 ms 9976 KB Output is correct
7 Correct 13 ms 9952 KB Output is correct
8 Correct 13 ms 9976 KB Output is correct
9 Correct 13 ms 9976 KB Output is correct
10 Correct 13 ms 9976 KB Output is correct
11 Correct 13 ms 9976 KB Output is correct
12 Correct 15 ms 10488 KB Output is correct
13 Correct 15 ms 10360 KB Output is correct
14 Correct 14 ms 10232 KB Output is correct
15 Correct 14 ms 10232 KB Output is correct
16 Incorrect 13 ms 10104 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 64496 KB Output is correct
2 Correct 549 ms 66336 KB Output is correct
3 Correct 596 ms 61380 KB Output is correct
4 Correct 492 ms 49968 KB Output is correct
5 Correct 496 ms 41000 KB Output is correct
6 Correct 508 ms 35372 KB Output is correct
7 Correct 387 ms 32796 KB Output is correct
8 Correct 298 ms 29564 KB Output is correct
9 Correct 277 ms 28596 KB Output is correct
10 Correct 281 ms 27848 KB Output is correct
11 Correct 276 ms 25924 KB Output is correct
12 Correct 394 ms 24380 KB Output is correct
13 Correct 490 ms 24184 KB Output is correct
14 Execution timed out 1078 ms 26268 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -