Submission #251599

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251599	2020-07-22T02:44:22 Z	rqi	Duathlon (APIO18_duathlon)	C++14	31 / 100	326 ms	31988 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
int pct(int x) { return __builtin_popcount(x); } 
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 
int fstTrue(function<bool(int)> f, int lo, int hi) {
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        int mid = (lo+hi)/2; 
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

// FILE I/O
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const int mx = 100005;
int n;
vi oadj[mx];
bool ovisited[mx];
vi olist;

void ogenList(int node){
    if(ovisited[node]) return;
    //dbg(node);
    ovisited[node] = 1;
    olist.pb(node);
    for(auto u: oadj[node]){
        ogenList(u);
    }
}

vi adj[mx];

int sub[mx];

void genSubs(int node, int prv = -1){
    sub[node] = 1;
    for(auto u: adj[node]){
        if(u == prv) continue;
        genSubs(u, node);
        sub[node]+=sub[u];
    }
}

ll treeSolve(int N){
    genSubs(1);
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        ans+=ll(N-1)*ll(N-1);
        for(auto u: adj[i]){
            if(sub[u] > sub[i]){
                ans-=(ll(N)-ll(sub[i]))*(ll(N)-ll(sub[i]));
            }
            else{
                ans-=ll(sub[u])*ll(sub[u]);
            }
        }
    }
    return ans;
}

ll cycSolve(int N){
    return ll(N)*ll(N-1)*ll(N-2);
}

int num[mx];
int par[mx];
vi children[mx];
bool visited[mx];

void dfs(int node, int prv = -1){
    visited[node] = 1;
    if(prv != -1){
        par[node] = prv;
        children[prv].pb(node);
    }
    for(auto u: adj[node]){
        if(u == prv) continue;
        if(visited[u]){
            if(num[u] == 1) continue;
            num[node]++;
            num[u]--;
            // dbg(node, u);
            continue;
        }
        dfs(u, node);
    }
}

void getnum(int node){
    for(auto u: children[node]){
        getnum(u);
        num[node]+=num[u];
    }
}

int cnt = 0;
map<int, int> m;
int csz[mx];

void genMap(int node){
    if(num[node] > 0){
        assert(num[node] == 1); //cactus
        m[node] = m[par[node]];
        csz[m[node]]++;
    }
    else{
        m[node] = ++cnt;
        csz[m[node]]++;
    }
    for(auto u: children[node]){
        genMap(u);
    }
}

vi tadj[mx];
int tsub[mx];

void genTsub(int node, int prv = -1){
    tsub[node]+=csz[node];
    for(auto u: tadj[node]){
        if(u == prv) continue;
        genTsub(u, node);
        tsub[node]+=tsub[u];
    }
}


ll tsolve(int N){
    genTsub(1);
    // for(int i = 1; i <= cnt; i++){
    //     dbg(i, tsub[i]);
    // }
    ll ans = 0;
    for(int i = 1; i <= cnt; i++){
        ans+=ll(csz[i])*ll(N-1)*ll(N-2);

        for(auto u: tadj[i]){
            if(tsub[u] > tsub[i]){
                ans-=ll(N-tsub[i])*ll(N-tsub[i]-1);
                ans-=ll(csz[i]-1)*ll(N-tsub[i]+1)*ll(N-tsub[i]);
            }
            else{
                ans-=ll(tsub[u])*ll(tsub[u]-1);
                ans-=ll(csz[i]-1)*ll(tsub[u]+1)*ll(tsub[u]);
            }
        }
        //dbg(i, ans);
    }
    return ans;
}

ll hardSolve(int N){ //CHANGE THIS! Do Cactus case as well
    cnt = 0;
    for(int i = 1; i <= N; i++){
        num[i] = par[i] = csz[i] = tsub[i] = 0;
        visited[i] = 0;
        children[i].clear();
        tadj[i].clear();
    }
    m.clear();

    dfs(1);
    // for(int i = 1; i <= N; i++){
    //     dbg(i, children[i]);
    // }
    // for(int i = 1; i <= N; i++){
    //     dbg(i, num[i]);
    // }
    getnum(1);
    // for(int i = 1; i <= N; i++){
    //     dbg(i, num[i]);
    // }
    genMap(1);
    // dbg(m);
    // for(int i = 1; i <= N; i++){
    //     dbg(i, csz[i]);
    // }
    for(int i = 1; i <= N; i++){
        for(auto u: adj[i]){
            if(m[i] != m[u]){
                tadj[m[i]].pb(m[u]);
            }
        }
    }
    // dbg(cnt);
    // for(int i = 1; i <= cnt; i++){
    //     dbg(tadj[i]);
    // }
    return tsolve(N);
}

ll solve(int N){
    bool isTree = 1;
    bool isCyc = 1;

    int tot = 0;
    for(int i = 1; i <= N; i++){
        tot+=sz(adj[i]);
        if(sz(adj[i]) > 2) isCyc = 0;
    }
    if(tot/2 != N-1){
        isTree = 0;
    }
    if(isTree){
        //dbg(hardSolve(N));
        //assert(hardSolve(N) == treeSolve(N));
        return treeSolve(N);
    }
    else if(isCyc){
        return cycSolve(N);
    }

    return hardSolve(N);
}

int main() {
    setIO();
    int m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        oadj[u].pb(v);
        oadj[v].pb(u);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(ovisited[i]) continue;
        //dbg(i);
        olist.clear();
        ogenList(i);
        map<int, int> m;
        for(int i = 0; i < sz(olist); i++){
            m[olist[i]] = i+1;
        }
        int N = sz(olist);
        for(int i = 1; i <= N; i++){
            adj[i].clear();
        }
        for(auto u: olist){
            for(auto x: oadj[u]){
                adj[m[u]].pb(m[x]);
            }
        }
        ans+=solve(N);
    }
    ps(ans);
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

count_triplets.cpp: In function 'void setIn(std::__cxx11::string)':
count_triplets.cpp:128:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void setOut(std::__cxx11::string)':
count_triplets.cpp:129:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	16 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	16 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	205 ms	25904 KB	Output is correct
2	Correct	201 ms	25836 KB	Output is correct
3	Correct	163 ms	19828 KB	Output is correct
4	Correct	186 ms	23016 KB	Output is correct
5	Correct	165 ms	17524 KB	Output is correct
6	Correct	160 ms	19828 KB	Output is correct
7	Correct	155 ms	15992 KB	Output is correct
8	Correct	157 ms	17528 KB	Output is correct
9	Correct	144 ms	14456 KB	Output is correct
10	Correct	152 ms	15608 KB	Output is correct
11	Correct	77 ms	12920 KB	Output is correct
12	Correct	76 ms	12792 KB	Output is correct
13	Correct	68 ms	12792 KB	Output is correct
14	Correct	68 ms	12664 KB	Output is correct
15	Correct	51 ms	12416 KB	Output is correct
16	Correct	55 ms	12280 KB	Output is correct
17	Correct	14 ms	9856 KB	Output is correct
18	Correct	15 ms	9856 KB	Output is correct
19	Correct	13 ms	9856 KB	Output is correct
20	Correct	13 ms	9856 KB	Output is correct
21	Correct	13 ms	9856 KB	Output is correct
22	Correct	13 ms	9856 KB	Output is correct

Subtask #4

10.0 / 10.0

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

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	175 ms	21744 KB	Output is correct
2	Correct	187 ms	21872 KB	Output is correct
3	Correct	194 ms	21804 KB	Output is correct
4	Correct	176 ms	21744 KB	Output is correct
5	Correct	185 ms	22004 KB	Output is correct
6	Correct	176 ms	24944 KB	Output is correct
7	Correct	180 ms	23920 KB	Output is correct
8	Correct	196 ms	23408 KB	Output is correct
9	Correct	185 ms	22768 KB	Output is correct
10	Correct	159 ms	18036 KB	Output is correct
11	Correct	168 ms	20720 KB	Output is correct
12	Correct	158 ms	15864 KB	Output is correct
13	Correct	140 ms	15472 KB	Output is correct
14	Correct	89 ms	13048 KB	Output is correct
15	Correct	65 ms	12920 KB	Output is correct
16	Correct	67 ms	12256 KB	Output is correct
17	Correct	152 ms	22384 KB	Output is correct
18	Correct	142 ms	22380 KB	Output is correct
19	Correct	145 ms	22376 KB	Output is correct
20	Correct	158 ms	22640 KB	Output is correct

Subtask #6

0 / 15.0

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

Subtask #7

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	21744 KB	Output is correct
2	Correct	208 ms	21748 KB	Output is correct
3	Incorrect	326 ms	31988 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	16 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	16 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-