Submission #60021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60021	2018-07-23T12:32:09 Z	dukati8	Duathlon (APIO18_duathlon)	C++14	5 / 100	238 ms	11288 KB

count_triplets

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
bool flags[100000];
bool visits[100000];
vector<pair<int,int> > roads;
vector< vector<int> > close;
long long tot=0;
long long dp1[100000];
long long dp2[100000];
long long numfixed[100000];
bool dfs(int curr, int goal) {
  if (curr==goal) {flags[curr]=true; return true;}
  visits[curr]=true;
  for (auto a:close[curr]) {
    if (!visits[a]) {
      if (dfs(a,goal)) {flags[curr]=true; return true;}
    }
  }
  return false;
}
bool bfs(int start, int goal) {
  queue<int> order;
  order.push(start);
  int from[60];
  while (!order.empty()) {
    int now = order.front();
    order.pop();
    if (now==goal) {
      flags[now]=true;
      while (now!=start){
        now=from[now];
        flags[now]=true;
      }
      return true;
    }
    for (auto a:close[now]) {
      if (!visits[a]) {
        from[a]=now;
        order.push(a);
        visits[a]=true;
      }
    }
  }
  return false;
}
void dpupdate(int curr) {
  if (!flags[curr] && (close[curr].size()-numfixed[curr]==1 || close[curr].size()-numfixed[curr]==0)) {
    flags[curr]=true;
    long long tempcount=0;
    for (auto o:close[curr]) {
      if (flags[o]) {
        tot+=dp2[o];
        tempcount+=dp1[o];
      }
    }
    for (auto o: close[curr]) {
      if (!flags[o]) {
        dp1[o]+=dp1[curr];
        dp2[o]+=dp1[curr]+dp2[curr];
        numfixed[o]++;
        dpupdate(o);
      }
      else {
        tot+=dp1[o]*(tempcount-dp1[o]);
      }
    }
  }
}
int main() {
  int n,m;
  cin >>n >>m;
  if (n<=10) {
    close.assign(n,vector<int>());
    rep(i,0,m) {
      int u,v;
      cin >> u >> v;
      u--;v--;
      roads.push_back(make_pair(u,v));
      close[u].push_back(v);
      close[v].push_back(u);
    }
    int counter=0;
    rep(i,0,n) {
      rep (j,0,n) {
        rep (k,0,n) {
          if (i!=j && j!=k && i!=k) {
            //search route i to j and j to k, and if not works try other way instead.
            rep (x,0,n) {visits[x]=false; flags[x]=false;}
            if (bfs(i,j)) {
              rep (x,0,n) visits[x]=flags[x];
              if (bfs(j,k)) {counter++;}
              else {
                rep (x,0,n) {visits[x]=false; flags[x]=false;}
                if (bfs(j,k)) {
                  rep (x,0,n) visits[x]=flags[x];
                  if (bfs(j,i)) {counter++;}
                }
              }
            }
          }
        }
      }
    }
    cout << counter << endl;
  }
  else {
    //antag inga cykler
    close.assign(n,vector<int>());
    rep(i,0,m) {
      int u,v;
      cin >> u >> v;
      u--;v--;
      roads.push_back(make_pair(u,v));
      close[u].push_back(v);
      close[v].push_back(u);
    }

    rep (i,0,n) {dp1[i]=1; dp2[i]=0; numfixed[i]=0;}
    rep (i,0,n) {
      dpupdate(i);
    }
    cout << 2*tot << endl;
  }

}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	420 KB	Output is correct
4	Correct	4 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	636 KB	Output is correct
9	Correct	3 ms	760 KB	Output is correct
10	Correct	3 ms	772 KB	Output is correct
11	Correct	4 ms	772 KB	Output is correct
12	Correct	4 ms	772 KB	Output is correct
13	Correct	3 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	3 ms	800 KB	Output is correct
16	Correct	3 ms	800 KB	Output is correct
17	Correct	3 ms	800 KB	Output is correct
18	Correct	3 ms	800 KB	Output is correct
19	Correct	3 ms	800 KB	Output is correct
20	Correct	2 ms	800 KB	Output is correct
21	Correct	3 ms	800 KB	Output is correct
22	Correct	4 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	3 ms	800 KB	Output is correct
25	Correct	3 ms	800 KB	Output is correct
26	Correct	5 ms	844 KB	Output is correct
27	Correct	3 ms	844 KB	Output is correct
28	Correct	3 ms	844 KB	Output is correct
29	Correct	3 ms	844 KB	Output is correct
30	Correct	2 ms	844 KB	Output is correct
31	Correct	4 ms	844 KB	Output is correct
32	Correct	4 ms	844 KB	Output is correct
33	Correct	4 ms	844 KB	Output is correct
34	Correct	3 ms	844 KB	Output is correct
35	Correct	3 ms	844 KB	Output is correct

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	420 KB	Output is correct
4	Correct	4 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	636 KB	Output is correct
9	Correct	3 ms	760 KB	Output is correct
10	Correct	3 ms	772 KB	Output is correct
11	Correct	4 ms	772 KB	Output is correct
12	Correct	4 ms	772 KB	Output is correct
13	Correct	3 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	3 ms	800 KB	Output is correct
16	Correct	3 ms	800 KB	Output is correct
17	Correct	3 ms	800 KB	Output is correct
18	Correct	3 ms	800 KB	Output is correct
19	Correct	3 ms	800 KB	Output is correct
20	Correct	2 ms	800 KB	Output is correct
21	Correct	3 ms	800 KB	Output is correct
22	Correct	4 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	3 ms	800 KB	Output is correct
25	Correct	3 ms	800 KB	Output is correct
26	Correct	5 ms	844 KB	Output is correct
27	Correct	3 ms	844 KB	Output is correct
28	Correct	3 ms	844 KB	Output is correct
29	Correct	3 ms	844 KB	Output is correct
30	Correct	2 ms	844 KB	Output is correct
31	Correct	4 ms	844 KB	Output is correct
32	Correct	4 ms	844 KB	Output is correct
33	Correct	4 ms	844 KB	Output is correct
34	Correct	3 ms	844 KB	Output is correct
35	Correct	3 ms	844 KB	Output is correct
36	Correct	3 ms	844 KB	Output is correct
37	Incorrect	4 ms	844 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	151 ms	10264 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	10264 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	238 ms	11288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	11288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	208 ms	11288 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	420 KB	Output is correct
4	Correct	4 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	636 KB	Output is correct
9	Correct	3 ms	760 KB	Output is correct
10	Correct	3 ms	772 KB	Output is correct
11	Correct	4 ms	772 KB	Output is correct
12	Correct	4 ms	772 KB	Output is correct
13	Correct	3 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	3 ms	800 KB	Output is correct
16	Correct	3 ms	800 KB	Output is correct
17	Correct	3 ms	800 KB	Output is correct
18	Correct	3 ms	800 KB	Output is correct
19	Correct	3 ms	800 KB	Output is correct
20	Correct	2 ms	800 KB	Output is correct
21	Correct	3 ms	800 KB	Output is correct
22	Correct	4 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	3 ms	800 KB	Output is correct
25	Correct	3 ms	800 KB	Output is correct
26	Correct	5 ms	844 KB	Output is correct
27	Correct	3 ms	844 KB	Output is correct
28	Correct	3 ms	844 KB	Output is correct
29	Correct	3 ms	844 KB	Output is correct
30	Correct	2 ms	844 KB	Output is correct
31	Correct	4 ms	844 KB	Output is correct
32	Correct	4 ms	844 KB	Output is correct
33	Correct	4 ms	844 KB	Output is correct
34	Correct	3 ms	844 KB	Output is correct
35	Correct	3 ms	844 KB	Output is correct
36	Correct	3 ms	844 KB	Output is correct
37	Incorrect	4 ms	844 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	3 ms	380 KB	Output is correct
3	Correct	3 ms	420 KB	Output is correct
4	Correct	4 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	636 KB	Output is correct
9	Correct	3 ms	760 KB	Output is correct
10	Correct	3 ms	772 KB	Output is correct
11	Correct	4 ms	772 KB	Output is correct
12	Correct	4 ms	772 KB	Output is correct
13	Correct	3 ms	772 KB	Output is correct
14	Correct	3 ms	772 KB	Output is correct
15	Correct	3 ms	800 KB	Output is correct
16	Correct	3 ms	800 KB	Output is correct
17	Correct	3 ms	800 KB	Output is correct
18	Correct	3 ms	800 KB	Output is correct
19	Correct	3 ms	800 KB	Output is correct
20	Correct	2 ms	800 KB	Output is correct
21	Correct	3 ms	800 KB	Output is correct
22	Correct	4 ms	800 KB	Output is correct
23	Correct	4 ms	800 KB	Output is correct
24	Correct	3 ms	800 KB	Output is correct
25	Correct	3 ms	800 KB	Output is correct
26	Correct	5 ms	844 KB	Output is correct
27	Correct	3 ms	844 KB	Output is correct
28	Correct	3 ms	844 KB	Output is correct
29	Correct	3 ms	844 KB	Output is correct
30	Correct	2 ms	844 KB	Output is correct
31	Correct	4 ms	844 KB	Output is correct
32	Correct	4 ms	844 KB	Output is correct
33	Correct	4 ms	844 KB	Output is correct
34	Correct	3 ms	844 KB	Output is correct
35	Correct	3 ms	844 KB	Output is correct
36	Correct	3 ms	844 KB	Output is correct
37	Incorrect	4 ms	844 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Submission #60021

Compilation message