oj.uz

Submission #288053

# Submission time Handle Problem Language Result Execution time Memory
288053 2020-09-01T08:19:34 Z ACmachine Duathlon (APIO18_duathlon) C++17
31 / 100
 539 ms 48348 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;
    map<int, int> edge_comp;
    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;
        map<int, vll> children2; // to x are joined children2[x]; 
        for(int id : g.adj[v]){
            edge<int> e = g.edges[id];
            int other = e.src ^ e.dest ^ v;
            int id2 = edge_comp[id];
            edge<int> e2 = g2.edges[id];
            int source = (bccd.bcc[e2.src] == v ? e2.src : e2.dest); 
            children2[source].pb(sz[other]);
            children.pb(sz[other]);
        }
        for(ll x : children){
            //ans -= ((ll)bccd.sz[v] - 1)*(x + 1)*x;
            ans -= x*(x-1); 
        }
        for(auto x : children2){
            ll sum = 0;
            for(ll y : x.ss) sum += y; 
            ans -= ((ll)bccd.sz[v] -1) * (sum + 1) * sum;
        }
        children.clear();
        children2.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]); 
                edge_comp[g.edges.size()-1] = id;
            }
        }
        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;
}

Compilation message

count_triplets.cpp: In member function 'void AcAutomaton::reroot(int, int)':
count_triplets.cpp:228:17: warning: unused variable 'id2' [-Wunused-variable]
  228 |             int id2 = edge_comp[id];
      |                 ^~~

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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 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 146 ms 25516 KB Output is correct
2 Correct 142 ms 25464 KB Output is correct
3 Correct 311 ms 36140 KB Output is correct
4 Correct 207 ms 27820 KB Output is correct
5 Correct 230 ms 29100 KB Output is correct
6 Correct 331 ms 34864 KB Output is correct
7 Correct 350 ms 31572 KB Output is correct
8 Correct 345 ms 32560 KB Output is correct
9 Correct 354 ms 29240 KB Output is correct
10 Correct 299 ms 28460 KB Output is correct
11 Correct 214 ms 23468 KB Output is correct
12 Correct 215 ms 23340 KB Output is correct
13 Correct 199 ms 23340 KB Output is correct
14 Correct 208 ms 22956 KB Output is correct
15 Correct 151 ms 21936 KB Output is correct
16 Correct 150 ms 21296 KB Output is correct
17 Correct 14 ms 10108 KB Output is correct
18 Correct 13 ms 10108 KB Output is correct
19 Correct 13 ms 10108 KB Output is correct
20 Correct 13 ms 10108 KB Output is correct
21 Correct 13 ms 10108 KB Output is correct
22 Correct 14 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 672 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 800 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 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 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 640 KB Output is correct
18 Correct 2 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 2 ms 640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 33196 KB Output is correct
2 Correct 472 ms 33196 KB Output is correct
3 Correct 478 ms 33584 KB Output is correct
4 Correct 486 ms 33196 KB Output is correct
5 Correct 490 ms 33324 KB Output is correct
6 Correct 529 ms 48348 KB Output is correct
7 Correct 535 ms 43308 KB Output is correct
8 Correct 539 ms 40880 KB Output is correct
9 Correct 514 ms 38316 KB Output is correct
10 Correct 478 ms 33196 KB Output is correct
11 Correct 482 ms 33324 KB Output is correct
12 Correct 473 ms 33324 KB Output is correct
13 Correct 474 ms 33196 KB Output is correct
14 Correct 429 ms 31660 KB Output is correct
15 Correct 361 ms 30124 KB Output is correct
16 Correct 205 ms 23984 KB Output is correct
17 Correct 274 ms 36780 KB Output is correct
18 Correct 297 ms 36780 KB Output is correct
19 Correct 304 ms 36652 KB Output is correct
20 Correct 323 ms 36012 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 2 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 486 ms 33196 KB Output is correct
2 Correct 478 ms 33196 KB Output is correct
3 Incorrect 351 ms 28460 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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 1 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -