Submission #251598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251598	2020-07-22T02:29:37 Z	rqi	Duathlon (APIO18_duathlon)	C++14	31 / 100	311 ms	33392 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(tsub[u]-tsub[i])*ll(tsub[u]-tsub[i]-1);
                ans-=ll(csz[i]-1)*ll(tsub[u]-tsub[i]+1)*ll(tsub[u]-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){
        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	180 ms	26860 KB	Output is correct
2	Correct	178 ms	27120 KB	Output is correct
3	Correct	172 ms	21244 KB	Output is correct
4	Correct	172 ms	24296 KB	Output is correct
5	Correct	173 ms	18804 KB	Output is correct
6	Correct	190 ms	21108 KB	Output is correct
7	Correct	164 ms	17144 KB	Output is correct
8	Correct	170 ms	18936 KB	Output is correct
9	Correct	127 ms	15736 KB	Output is correct
10	Correct	146 ms	16888 KB	Output is correct
11	Correct	66 ms	13944 KB	Output is correct
12	Correct	64 ms	13944 KB	Output is correct
13	Correct	56 ms	13816 KB	Output is correct
14	Correct	59 ms	13688 KB	Output is correct
15	Correct	51 ms	13176 KB	Output is correct
16	Correct	46 ms	13048 KB	Output is correct
17	Correct	13 ms	9856 KB	Output is correct
18	Correct	14 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	6 ms	9856 KB	Output is correct
2	Correct	6 ms	9856 KB	Output is correct
3	Correct	6 ms	9856 KB	Output is correct
4	Correct	7 ms	9984 KB	Output is correct
5	Correct	7 ms	9856 KB	Output is correct
6	Correct	7 ms	9856 KB	Output is correct
7	Correct	6 ms	9856 KB	Output is correct
8	Correct	7 ms	9856 KB	Output is correct
9	Correct	6 ms	9856 KB	Output is correct
10	Correct	6 ms	9856 KB	Output is correct
11	Correct	7 ms	9856 KB	Output is correct
12	Correct	6 ms	9856 KB	Output is correct
13	Correct	6 ms	9856 KB	Output is correct
14	Correct	6 ms	9856 KB	Output is correct
15	Correct	6 ms	9856 KB	Output is correct
16	Correct	6 ms	9728 KB	Output is correct
17	Correct	6 ms	9856 KB	Output is correct
18	Correct	7 ms	9856 KB	Output is correct
19	Correct	6 ms	9856 KB	Output is correct
20	Correct	6 ms	9856 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	187 ms	22976 KB	Output is correct
2	Correct	183 ms	22896 KB	Output is correct
3	Correct	175 ms	22768 KB	Output is correct
4	Correct	176 ms	22764 KB	Output is correct
5	Correct	176 ms	22768 KB	Output is correct
6	Correct	179 ms	25972 KB	Output is correct
7	Correct	189 ms	24964 KB	Output is correct
8	Correct	209 ms	24432 KB	Output is correct
9	Correct	211 ms	23792 KB	Output is correct
10	Correct	186 ms	19060 KB	Output is correct
11	Correct	198 ms	21744 KB	Output is correct
12	Correct	147 ms	16888 KB	Output is correct
13	Correct	137 ms	16376 KB	Output is correct
14	Correct	79 ms	14072 KB	Output is correct
15	Correct	65 ms	13816 KB	Output is correct
16	Correct	45 ms	12792 KB	Output is correct
17	Correct	137 ms	23404 KB	Output is correct
18	Correct	145 ms	23404 KB	Output is correct
19	Correct	157 ms	23528 KB	Output is correct
20	Correct	152 ms	23408 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 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	185 ms	22000 KB	Output is correct
2	Correct	186 ms	21944 KB	Output is correct
3	Incorrect	311 ms	33392 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	-