oj.uz

Submission #288158

# Submission time Handle Problem Language Result Execution time Memory
288158 2020-09-01T09:23:43 Z ACmachine Duathlon (APIO18_duathlon) C++17
66 / 100
 531 ms 48216 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[id2];
            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 -= 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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 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 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 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 1 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 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 25516 KB Output is correct
2 Correct 142 ms 25516 KB Output is correct
3 Correct 313 ms 36268 KB Output is correct
4 Correct 203 ms 27816 KB Output is correct
5 Correct 245 ms 29132 KB Output is correct
6 Correct 333 ms 34988 KB Output is correct
7 Correct 337 ms 31664 KB Output is correct
8 Correct 352 ms 32556 KB Output is correct
9 Correct 340 ms 29228 KB Output is correct
10 Correct 300 ms 28460 KB Output is correct
11 Correct 211 ms 23468 KB Output is correct
12 Correct 222 ms 23344 KB Output is correct
13 Correct 200 ms 23340 KB Output is correct
14 Correct 193 ms 22952 KB Output is correct
15 Correct 168 ms 21936 KB Output is correct
16 Correct 155 ms 21296 KB Output is correct
17 Correct 13 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 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 896 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 896 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 3 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 600 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 474 ms 33232 KB Output is correct
2 Correct 483 ms 33300 KB Output is correct
3 Correct 479 ms 33196 KB Output is correct
4 Correct 468 ms 33324 KB Output is correct
5 Correct 464 ms 33196 KB Output is correct
6 Correct 531 ms 48216 KB Output is correct
7 Correct 515 ms 43668 KB Output is correct
8 Correct 510 ms 41004 KB Output is correct
9 Correct 472 ms 38188 KB Output is correct
10 Correct 488 ms 33196 KB Output is correct
11 Correct 482 ms 33324 KB Output is correct
12 Correct 498 ms 33196 KB Output is correct
13 Correct 481 ms 33236 KB Output is correct
14 Correct 406 ms 31648 KB Output is correct
15 Correct 363 ms 29996 KB Output is correct
16 Correct 199 ms 23984 KB Output is correct
17 Correct 268 ms 36908 KB Output is correct
18 Correct 280 ms 36012 KB Output is correct
19 Correct 281 ms 36268 KB Output is correct
20 Correct 302 ms 35500 KB Output is correct

Subtask #6
15.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 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 3 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 512 KB Output is correct
18 Correct 2 ms 528 KB Output is correct
19 Correct 1 ms 512 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 640 KB Output is correct
22 Correct 2 ms 640 KB Output is correct
23 Correct 2 ms 640 KB Output is correct
24 Correct 2 ms 640 KB Output is correct
25 Correct 1 ms 512 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 1 ms 512 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 33300 KB Output is correct
2 Correct 471 ms 33212 KB Output is correct
3 Correct 361 ms 28460 KB Output is correct
4 Correct 259 ms 23596 KB Output is correct
5 Correct 184 ms 20012 KB Output is correct
6 Correct 173 ms 18760 KB Output is correct
7 Correct 143 ms 18220 KB Output is correct
8 Correct 131 ms 17452 KB Output is correct
9 Correct 124 ms 17196 KB Output is correct
10 Correct 135 ms 17068 KB Output is correct
11 Correct 151 ms 16556 KB Output is correct
12 Correct 123 ms 16428 KB Output is correct
13 Correct 116 ms 16556 KB Output is correct
14 Correct 126 ms 18604 KB Output is correct
15 Correct 381 ms 37036 KB Output is correct
16 Correct 367 ms 34220 KB Output is correct
17 Correct 312 ms 32172 KB Output is correct
18 Correct 307 ms 29868 KB Output is correct
19 Correct 241 ms 23732 KB Output is correct
20 Correct 243 ms 23596 KB Output is correct
21 Correct 251 ms 23596 KB Output is correct
22 Correct 208 ms 22188 KB Output is correct
23 Correct 166 ms 20524 KB Output is correct
24 Correct 279 ms 29740 KB Output is correct
25 Correct 273 ms 29612 KB Output is correct
26 Correct 225 ms 27180 KB Output is correct
27 Correct 224 ms 26284 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 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 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 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 1 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 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -