Submission #911486

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
911486	2024-01-19 02:00:40	prairie2022	Duathlon (APIO18_duathlon)	C++17	31 / 100	87 ms	27220 KiB

count_triplets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
typedef long long ll;
const int M = 1e5+1;
vector<int> e[M];
int dfn[M], dfc;
int stk[M], top = -1, num;
vector<int> bct[M<<1];
int tarjan(int u){ // return low
  dfn[u] = ++dfc;
  stk[++top] = u;
  int low = dfn[u];
  for(const int &v: e[u]){
    if(dfn[v]) low = min(low, dfn[v]);
    else{
      int tmp = tarjan(v);
      if(tmp==dfn[u]){
        bct[++num].push_back(u);
        while(stk[top]!=u) bct[num].push_back(stk[top--]);
        for(const int &w: bct[num]) bct[w].push_back(num);
      }
      else low = min(low, tmp);
    }
  }
  return low;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10