Submission #251601

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251601	2020-07-22T02:45:53 Z	rqi	Duathlon (APIO18_duathlon)	C++14	31 / 100	381 ms	37232 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 'll solve(int)':
count_triplets.cpp:317:10: warning: variable 'isTree' set but not used [-Wunused-but-set-variable]
     bool isTree = 1;
          ^~~~~~
count_triplets.cpp:318:10: warning: variable 'isCyc' set but not used [-Wunused-but-set-variable]
     bool isCyc = 1;
          ^~~~~
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	17 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	17 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	317 ms	36932 KB	Output is correct
2	Correct	304 ms	36976 KB	Output is correct
3	Correct	266 ms	26484 KB	Output is correct
4	Correct	282 ms	31972 KB	Output is correct
5	Correct	256 ms	22008 KB	Output is correct
6	Correct	262 ms	26612 KB	Output is correct
7	Correct	234 ms	18424 KB	Output is correct
8	Correct	249 ms	22392 KB	Output is correct
9	Correct	206 ms	15736 KB	Output is correct
10	Correct	226 ms	18164 KB	Output is correct
11	Correct	102 ms	12920 KB	Output is correct
12	Correct	95 ms	12904 KB	Output is correct
13	Correct	83 ms	12796 KB	Output is correct
14	Correct	82 ms	12792 KB	Output is correct
15	Correct	61 ms	12536 KB	Output is correct
16	Correct	68 ms	12280 KB	Output is correct
17	Correct	22 ms	9856 KB	Output is correct
18	Correct	21 ms	9856 KB	Output is correct
19	Correct	20 ms	9856 KB	Output is correct
20	Correct	32 ms	9856 KB	Output is correct
21	Correct	28 ms	9856 KB	Output is correct
22	Correct	33 ms	9856 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	9984 KB	Output is correct
2	Correct	8 ms	10044 KB	Output is correct
3	Correct	14 ms	9984 KB	Output is correct
4	Correct	11 ms	9984 KB	Output is correct
5	Correct	11 ms	9984 KB	Output is correct
6	Correct	16 ms	9984 KB	Output is correct
7	Correct	7 ms	9984 KB	Output is correct
8	Correct	10 ms	9984 KB	Output is correct
9	Correct	10 ms	9984 KB	Output is correct
10	Correct	8 ms	9984 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct
12	Correct	9 ms	9856 KB	Output is correct
13	Correct	10 ms	9856 KB	Output is correct
14	Correct	7 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	8 ms	9984 KB	Output is correct
18	Correct	7 ms	9984 KB	Output is correct
19	Correct	7 ms	9984 KB	Output is correct
20	Correct	8 ms	9984 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	329 ms	32672 KB	Output is correct
2	Correct	314 ms	32592 KB	Output is correct
3	Correct	316 ms	32568 KB	Output is correct
4	Correct	323 ms	32624 KB	Output is correct
5	Correct	324 ms	32648 KB	Output is correct
6	Correct	328 ms	37232 KB	Output is correct
7	Correct	336 ms	35268 KB	Output is correct
8	Correct	361 ms	34672 KB	Output is correct
9	Correct	381 ms	33900 KB	Output is correct
10	Correct	308 ms	24336 KB	Output is correct
11	Correct	307 ms	30320 KB	Output is correct
12	Correct	281 ms	19784 KB	Output is correct
13	Correct	245 ms	18552 KB	Output is correct
14	Correct	113 ms	13048 KB	Output is correct
15	Correct	102 ms	12852 KB	Output is correct
16	Correct	61 ms	12280 KB	Output is correct
17	Correct	241 ms	32228 KB	Output is correct
18	Correct	254 ms	32364 KB	Output is correct
19	Correct	259 ms	32360 KB	Output is correct
20	Correct	252 ms	32312 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	9984 KB	Output is correct
2	Correct	8 ms	9984 KB	Output is correct
3	Incorrect	8 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	299 ms	32616 KB	Output is correct
2	Correct	320 ms	32908 KB	Output is correct
3	Incorrect	306 ms	31984 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	17 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	17 ms	19584 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-