oj.uz

Submission #287568

# Submission time Handle Problem Language Result Execution time Memory
287568 2020-08-31T20:10:55 Z ACmachine Duathlon (APIO18_duathlon) C++17
31 / 100
 342 ms 35756 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 

const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

// centroid decomposition of a biconnected component tree dafuq
// first only centoid decomp to pass those subtasks

template<typename T>
struct edge{
    int src;
    int dest;
    T cost;
};
template<typename T>
class graph{
    public: 
    vector<edge<T>> edges;
    vector<vector<int>> adj;
    int n;
    graph(){};
    graph(int _n){
        n = _n;
        adj.resize(n);
    }
};

template<typename T>
class undigraph : public graph<T>{
    public:
        using graph<T>::edges;
        using graph<T>::adj;
        using graph<T>::n;
        undigraph() : graph<T>(){};
        undigraph(int _n) : graph<T>(_n){};

        int add_edge(int src, int dest, T cost = 1){
            int id = edges.size();
            edges.push_back({src, dest, cost});
            adj[src].push_back(id);
            adj[dest].push_back(id);
            return id;
        }
};
struct bcc_decomposition{
    graph<int> g; 
    vi bcc;
    vi low, in;
    vector<bool> isbridge;
    int t = 0;
    vi sz;
    void init(){
        bcc.resize(g.n, -1);
        low.resize(g.n); in.resize(g.n, -1);
        isbridge.resize(g.edges.size(), false); 
    }
    void get_bridges(int v, int p){
        in[v] = t++;
        low[v] = INF;
        for(int id : g.adj[v]){
            edge<int> e = g.edges[id];
            int other = e.src ^ e.dest ^ v;
            if(other == p) continue;
            if(in[other] == -1){
                get_bridges(other, v);
                if(low[other] > in[v]){
                    isbridge[id] = true;
                }
                low[v] = min(low[v], low[other]);
            }
            else if(in[v] > in[other]){
                low[v] = min(low[v], in[other]);
            }
        }
    }
    int cnt = 0;
    void decompose(){
        REP(i, g.n){
            if(in[i] == -1) get_bridges(i, -1);
        }
        function<void(int)> dfs = [&](int v){
            bcc[v] = cnt;
            for(int id : g.adj[v]){
                if(isbridge[id]) continue;
                edge<int> e = g.edges[id];
                int other = e.src ^ e.dest ^ v;
                if(bcc[other] == -1) dfs(other);
            }
        };
        REP(i, g.n){
            if(bcc[i] == -1){
                dfs(i);
                ++cnt;
            }
        }
        sz.rsz(cnt, 0);
        REP(i, g.n) sz[bcc[i]]++;
    }
};
struct AcAutomaton{
    int n, m;
    undigraph<int> g2;
    undigraph<int> g;
    bcc_decomposition bccd;
	void read_in(){
		cin >> n >> m;
        g2 = undigraph<int>(n);
        REP(i, m){
            pii e; cin >> e;
            e.ff--; e.ss--;
            g2.add_edge(e.ff, e.ss);
        }
	}
    ll ans = 0;
    vi sz;
    vi roots;
    void get_sz(){
        sz.resize(g.n);
        vector<bool> visited(g.n, false);
        function<void(int, int)> dfs = [&](int v, int p){
            sz[v] = bccd.sz[v];
            visited[v] = true;
            for(int id : g.adj[v]){
                edge<int> e = g.edges[id];
                int other = e.src ^ e.dest ^ v;
                if(other != p){
                    dfs(other, v);
                    sz[v] += sz[other];
                }
            }
        };
        REP(i, g.n){
            if(!visited[i]){
                roots.pb(i);
                dfs(i, -1);
            }
        }
    } 
    void reroot(int v, int p){
        if(p != -1){
            sz[p] -= sz[v];
            sz[v] += sz[p];
        }
        // process;
        vll children;
        for(int id : g.adj[v]){
            edge<int> e = g.edges[id];
            int other = e.src ^ e.dest ^ v;
            children.pb(sz[other]);
        }
        for(ll x : children){
            ans -= ((ll)bccd.sz[v] - 1)*(x + 1)*x;
            ans -= x*(x-1); 
        }
        children.clear();
        for(int id : g.adj[v]){
            edge<int> e = g.edges[id];
            int other = e.src ^ e.dest ^ v;
            if(other != p) reroot(other, v);
        }
        if(p != -1){
            sz[v] -= sz[p];
            sz[p] += sz[v];
        }
    }
	void solve(){
        bccd.g = g2;
        bccd.init();
        bccd.decompose();
        g = undigraph<int> (bccd.cnt);
        set<int> added;
        REP(i, g2.n){
            for(int id : g2.adj[i]){
                edge<int> e = g2.edges[id];
                int other = e.src ^ e.dest ^ i;
                if(bccd.bcc[i] == bccd.bcc[other]) continue;
                if(added.find(id) != added.end()) continue;
                added.insert(id);
                g.add_edge(bccd.bcc[i], bccd.bcc[other]); 
            }
        }
        get_sz();
        for(auto x : roots){
            ans += ((ll)sz[x] * ((ll)sz[x]-1) * ((ll)sz[x]-2));
        }
        for(auto x : roots) reroot(x, -1); 
	    cout << ans << endl; 
	}
};
    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int tcase = 1;
	while(tcase--){
		AcAutomaton solver;
		solver.read_in();
		solver.solve();
	}
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 24492 KB Output is correct
2 Correct 126 ms 25388 KB Output is correct
3 Correct 218 ms 28588 KB Output is correct
4 Correct 163 ms 26668 KB Output is correct
5 Correct 190 ms 24380 KB Output is correct
6 Correct 230 ms 28204 KB Output is correct
7 Correct 233 ms 26412 KB Output is correct
8 Correct 242 ms 26924 KB Output is correct
9 Correct 234 ms 25004 KB Output is correct
10 Correct 199 ms 24364 KB Output is correct
11 Correct 156 ms 21676 KB Output is correct
12 Correct 153 ms 21552 KB Output is correct
13 Correct 136 ms 21676 KB Output is correct
14 Correct 139 ms 21164 KB Output is correct
15 Correct 115 ms 20400 KB Output is correct
16 Correct 118 ms 19760 KB Output is correct
17 Correct 12 ms 10108 KB Output is correct
18 Correct 12 ms 10108 KB Output is correct
19 Correct 12 ms 10108 KB Output is correct
20 Correct 12 ms 10108 KB Output is correct
21 Correct 12 ms 9980 KB Output is correct
22 Correct 12 ms 9980 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 544 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 640 KB Output is correct
18 Correct 1 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 1 ms 640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 27564 KB Output is correct
2 Correct 322 ms 27564 KB Output is correct
3 Correct 308 ms 27436 KB Output is correct
4 Correct 304 ms 27436 KB Output is correct
5 Correct 295 ms 27440 KB Output is correct
6 Correct 337 ms 35756 KB Output is correct
7 Correct 337 ms 33068 KB Output is correct
8 Correct 333 ms 31792 KB Output is correct
9 Correct 336 ms 30380 KB Output is correct
10 Correct 299 ms 27560 KB Output is correct
11 Correct 306 ms 28460 KB Output is correct
12 Correct 342 ms 28460 KB Output is correct
13 Correct 318 ms 28460 KB Output is correct
14 Correct 274 ms 27436 KB Output is correct
15 Correct 256 ms 26232 KB Output is correct
16 Correct 144 ms 21556 KB Output is correct
17 Correct 171 ms 31276 KB Output is correct
18 Correct 184 ms 30764 KB Output is correct
19 Correct 199 ms 30764 KB Output is correct
20 Correct 186 ms 30380 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Incorrect 1 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 27436 KB Output is correct
2 Correct 323 ms 27308 KB Output is correct
3 Incorrect 243 ms 24108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 0 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -