oj.uz

답안 #287552

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287552 2020-08-31T20:00:15 Z ACmachine 철인 이종 경기 (APIO18_duathlon) C++17
23 / 100
 353 ms 35436 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);
            }
        }
    }
    ll ans2 = 0;
    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]);
        }
        ll sum = 0;
        for(ll x : children) sum += x;
        for(ll x : children){
            ans -= ((ll)bccd.sz[v] - 1)*(x + 1)*x;
            ans -= x*(x-1);
            ans2 += x * (sum - x);
        }
        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(){
        ans += ((ll)g2.n * ((ll)g2.n -1) * ((ll)g2.n-2));
        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) reroot(x, -1); 
		cout << ans2 << 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 134 ms 24244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 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 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 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 2 ms 640 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 27180 KB Output is correct
2 Correct 314 ms 27244 KB Output is correct
3 Correct 319 ms 27308 KB Output is correct
4 Correct 305 ms 27308 KB Output is correct
5 Correct 316 ms 27328 KB Output is correct
6 Correct 342 ms 35436 KB Output is correct
7 Correct 353 ms 33068 KB Output is correct
8 Correct 334 ms 31404 KB Output is correct
9 Correct 340 ms 30380 KB Output is correct
10 Correct 307 ms 27180 KB Output is correct
11 Correct 313 ms 28592 KB Output is correct
12 Correct 332 ms 28532 KB Output is correct
13 Correct 317 ms 28588 KB Output is correct
14 Correct 274 ms 27436 KB Output is correct
15 Correct 248 ms 26292 KB Output is correct
16 Correct 146 ms 21552 KB Output is correct
17 Correct 173 ms 31404 KB Output is correct
18 Correct 183 ms 30764 KB Output is correct
19 Correct 193 ms 30764 KB Output is correct
20 Correct 195 ms 30380 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Incorrect 2 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 27308 KB Output is correct
2 Correct 330 ms 27100 KB Output is correct
3 Incorrect 251 ms 23852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -