oj.uz

Submission #993993

# Submission time Handle Problem Language Result Execution time Memory
993993 2024-06-07T01:01:48 Z vjudge1 Duathlon (APIO18_duathlon) C++17
49 / 100
 82 ms 56992 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 300100
int dep[N],id[N],low[N],CC,CC2,in[N],par[N],nod1,nod2,sz[N],ans;
struct unionfind{
    int par[N];
    int abp(int n){
        return(par[n]==n?n:par[n]=abp(par[n]));
    }
    void init(){
        for(int i=0;i<N;i++)
            par[i]=i;
    }
    void merge(int a,int b){
        a=abp(a),b=abp(b);
        if(a-b)par[a]=b;
    }
} CYCLE;
set<pair<int,int>>st[N];
vector<int>adj1[N],adj2[N];
void tarjan(int n,int p){
    nod1++;
    low[n]=id[n]=++CC2;
    for(auto i:adj1[n]){
        if(i==p)continue;
        if(!id[i]){
            dep[i]=dep[n]+1;
            tarjan(i,n);
            low[n]=min(low[n],low[i]);
            if(low[i]>id[n])
                adj2[n].push_back(i);
        } else if(dep[i]<dep[n])
            st[n].insert({dep[i],++CC}),
            low[n]=min(low[n],low[i]);
    }
}
void dfscyc(int n){
    for(auto i:adj1[n]){
        if(dep[i]-dep[n]-1)
            continue;
        dfscyc(i);
        if(st[i].size()&&st[i].begin()->first<dep[n]){
            if(st[n].size()) CYCLE.merge(st[i].begin()
                        ->second,st[n].begin()->second);
            st[n].insert(*st[i].begin());
        }
    }
    if(st[n].size())
        in[n]=st[n].begin()->second;
}
void dfs2(int n,int p){
    for(auto i:adj1[n])
        if(dep[i]==dep[n]+1)
            dfs2(i,n);
    adj2[CYCLE.abp(in[n])].push_back(n);
    par[CYCLE.abp(in[n])]=p;
}
void dfs3(int n){
    long long sum=0,x;
    for(auto i:adj2[n]){
        dfs3(i);
        sum+=sz[n]*sz[i];
        sz[n]+=sz[i];
    }
    x=sz[n];
    sz[n]+=n<=nod2;
    sum+=(nod1-sz[n])*x;
    ans+=(n>nod2?adj2[n].size()-1:1)*sum*2;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    CYCLE.init();
    int n,m;
    cin>>n>>m;
    CC=nod2=n;
    while(m--){
        int a,b;
        cin>>a>>b;
        adj1[a].push_back(b);
        adj1[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        if(!id[i]){
            nod1=0;
            int prv=CC;
            tarjan(i,0),
            dfscyc(i),dfs2(i,0);
            for(int j=prv;j++<CC;)
                if(CYCLE.par[j]==j)
                    adj2[par[j]].push_back(j);
            dfs3(i);
        }
    cout<<ans<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33372 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 5 ms 33244 KB Output is correct
9 Correct 5 ms 33372 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33372 KB Output is correct
12 Correct 5 ms 33236 KB Output is correct
13 Correct 5 ms 33372 KB Output is correct
14 Correct 5 ms 33372 KB Output is correct
15 Correct 5 ms 33372 KB Output is correct
16 Correct 5 ms 33372 KB Output is correct
17 Correct 5 ms 33424 KB Output is correct
18 Correct 5 ms 33372 KB Output is correct
19 Correct 5 ms 33416 KB Output is correct
20 Correct 5 ms 33372 KB Output is correct
21 Correct 5 ms 33468 KB Output is correct
22 Correct 5 ms 33480 KB Output is correct
23 Correct 5 ms 33240 KB Output is correct
24 Correct 5 ms 33372 KB Output is correct
25 Correct 5 ms 33460 KB Output is correct
26 Correct 5 ms 33236 KB Output is correct
27 Correct 5 ms 33372 KB Output is correct
28 Correct 5 ms 33372 KB Output is correct
29 Correct 5 ms 33372 KB Output is correct
30 Correct 5 ms 33372 KB Output is correct
31 Correct 5 ms 33420 KB Output is correct
32 Correct 5 ms 33476 KB Output is correct
33 Correct 5 ms 33368 KB Output is correct
34 Correct 6 ms 33372 KB Output is correct
35 Correct 5 ms 33372 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33372 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 5 ms 33244 KB Output is correct
9 Correct 5 ms 33372 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33372 KB Output is correct
12 Correct 5 ms 33236 KB Output is correct
13 Correct 5 ms 33372 KB Output is correct
14 Correct 5 ms 33372 KB Output is correct
15 Correct 5 ms 33372 KB Output is correct
16 Correct 5 ms 33372 KB Output is correct
17 Correct 5 ms 33424 KB Output is correct
18 Correct 5 ms 33372 KB Output is correct
19 Correct 5 ms 33416 KB Output is correct
20 Correct 5 ms 33372 KB Output is correct
21 Correct 5 ms 33468 KB Output is correct
22 Correct 5 ms 33480 KB Output is correct
23 Correct 5 ms 33240 KB Output is correct
24 Correct 5 ms 33372 KB Output is correct
25 Correct 5 ms 33460 KB Output is correct
26 Correct 5 ms 33236 KB Output is correct
27 Correct 5 ms 33372 KB Output is correct
28 Correct 5 ms 33372 KB Output is correct
29 Correct 5 ms 33372 KB Output is correct
30 Correct 5 ms 33372 KB Output is correct
31 Correct 5 ms 33420 KB Output is correct
32 Correct 5 ms 33476 KB Output is correct
33 Correct 5 ms 33368 KB Output is correct
34 Correct 6 ms 33372 KB Output is correct
35 Correct 5 ms 33372 KB Output is correct
36 Correct 5 ms 33372 KB Output is correct
37 Correct 5 ms 33464 KB Output is correct
38 Correct 6 ms 33372 KB Output is correct
39 Correct 5 ms 33372 KB Output is correct
40 Correct 6 ms 33372 KB Output is correct
41 Correct 5 ms 33424 KB Output is correct
42 Correct 5 ms 33472 KB Output is correct
43 Correct 5 ms 33372 KB Output is correct
44 Correct 5 ms 33476 KB Output is correct
45 Correct 5 ms 33368 KB Output is correct
46 Correct 5 ms 33372 KB Output is correct
47 Correct 5 ms 33368 KB Output is correct
48 Correct 5 ms 33372 KB Output is correct
49 Correct 6 ms 33372 KB Output is correct
50 Correct 5 ms 33368 KB Output is correct
51 Correct 5 ms 33476 KB Output is correct
52 Correct 5 ms 33372 KB Output is correct
53 Correct 6 ms 33368 KB Output is correct
54 Correct 5 ms 33372 KB Output is correct
55 Correct 5 ms 33372 KB Output is correct
56 Correct 5 ms 33372 KB Output is correct
57 Correct 5 ms 33372 KB Output is correct
58 Correct 5 ms 33372 KB Output is correct
59 Correct 5 ms 33236 KB Output is correct
60 Correct 5 ms 33372 KB Output is correct
61 Correct 5 ms 33372 KB Output is correct
62 Correct 6 ms 33372 KB Output is correct
63 Correct 5 ms 33416 KB Output is correct
64 Correct 6 ms 33372 KB Output is correct
65 Correct 6 ms 33372 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33372 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 5 ms 33372 KB Output is correct
7 Correct 8 ms 33372 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 6 ms 33372 KB Output is correct
10 Correct 6 ms 33368 KB Output is correct
11 Correct 6 ms 33472 KB Output is correct
12 Correct 6 ms 33624 KB Output is correct
13 Correct 6 ms 33372 KB Output is correct
14 Correct 6 ms 33460 KB Output is correct
15 Correct 7 ms 33368 KB Output is correct
16 Correct 6 ms 33372 KB Output is correct
17 Correct 6 ms 33368 KB Output is correct
18 Correct 5 ms 33372 KB Output is correct
19 Correct 5 ms 33372 KB Output is correct
20 Correct 5 ms 33372 KB Output is correct
21 Correct 5 ms 33372 KB Output is correct
22 Correct 5 ms 33372 KB Output is correct
23 Correct 5 ms 33372 KB Output is correct
24 Correct 7 ms 33500 KB Output is correct
25 Correct 5 ms 33372 KB Output is correct
26 Correct 5 ms 33372 KB Output is correct
27 Correct 5 ms 33372 KB Output is correct

Subtask #7
0 / 20.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33372 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 5 ms 33244 KB Output is correct
9 Correct 5 ms 33372 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33372 KB Output is correct
12 Correct 5 ms 33236 KB Output is correct
13 Correct 5 ms 33372 KB Output is correct
14 Correct 5 ms 33372 KB Output is correct
15 Correct 5 ms 33372 KB Output is correct
16 Correct 5 ms 33372 KB Output is correct
17 Correct 5 ms 33424 KB Output is correct
18 Correct 5 ms 33372 KB Output is correct
19 Correct 5 ms 33416 KB Output is correct
20 Correct 5 ms 33372 KB Output is correct
21 Correct 5 ms 33468 KB Output is correct
22 Correct 5 ms 33480 KB Output is correct
23 Correct 5 ms 33240 KB Output is correct
24 Correct 5 ms 33372 KB Output is correct
25 Correct 5 ms 33460 KB Output is correct
26 Correct 5 ms 33236 KB Output is correct
27 Correct 5 ms 33372 KB Output is correct
28 Correct 5 ms 33372 KB Output is correct
29 Correct 5 ms 33372 KB Output is correct
30 Correct 5 ms 33372 KB Output is correct
31 Correct 5 ms 33420 KB Output is correct
32 Correct 5 ms 33476 KB Output is correct
33 Correct 5 ms 33368 KB Output is correct
34 Correct 6 ms 33372 KB Output is correct
35 Correct 5 ms 33372 KB Output is correct
36 Correct 5 ms 33372 KB Output is correct
37 Correct 5 ms 33464 KB Output is correct
38 Correct 6 ms 33372 KB Output is correct
39 Correct 5 ms 33372 KB Output is correct
40 Correct 6 ms 33372 KB Output is correct
41 Correct 5 ms 33424 KB Output is correct
42 Correct 5 ms 33472 KB Output is correct
43 Correct 5 ms 33372 KB Output is correct
44 Correct 5 ms 33476 KB Output is correct
45 Correct 5 ms 33368 KB Output is correct
46 Correct 5 ms 33372 KB Output is correct
47 Correct 5 ms 33368 KB Output is correct
48 Correct 5 ms 33372 KB Output is correct
49 Correct 6 ms 33372 KB Output is correct
50 Correct 5 ms 33368 KB Output is correct
51 Correct 5 ms 33476 KB Output is correct
52 Correct 5 ms 33372 KB Output is correct
53 Correct 6 ms 33368 KB Output is correct
54 Correct 5 ms 33372 KB Output is correct
55 Correct 5 ms 33372 KB Output is correct
56 Correct 5 ms 33372 KB Output is correct
57 Correct 5 ms 33372 KB Output is correct
58 Correct 5 ms 33372 KB Output is correct
59 Correct 5 ms 33236 KB Output is correct
60 Correct 5 ms 33372 KB Output is correct
61 Correct 5 ms 33372 KB Output is correct
62 Correct 6 ms 33372 KB Output is correct
63 Correct 5 ms 33416 KB Output is correct
64 Correct 6 ms 33372 KB Output is correct
65 Correct 6 ms 33372 KB Output is correct
66 Correct 5 ms 33372 KB Output is correct
67 Correct 5 ms 33372 KB Output is correct
68 Correct 6 ms 33384 KB Output is correct
69 Correct 6 ms 33628 KB Output is correct
70 Correct 6 ms 33460 KB Output is correct
71 Correct 6 ms 33372 KB Output is correct
72 Correct 6 ms 33372 KB Output is correct
73 Correct 5 ms 33372 KB Output is correct
74 Correct 5 ms 33372 KB Output is correct
75 Correct 5 ms 33372 KB Output is correct
76 Correct 5 ms 33476 KB Output is correct
77 Correct 5 ms 33420 KB Output is correct
78 Correct 5 ms 33468 KB Output is correct
79 Correct 6 ms 33372 KB Output is correct
80 Correct 5 ms 33372 KB Output is correct
81 Correct 6 ms 33372 KB Output is correct
82 Correct 6 ms 33672 KB Output is correct
83 Correct 5 ms 33628 KB Output is correct
84 Correct 6 ms 33628 KB Output is correct
85 Correct 6 ms 33372 KB Output is correct
86 Correct 5 ms 33372 KB Output is correct
87 Correct 5 ms 33372 KB Output is correct
88 Correct 5 ms 33372 KB Output is correct
89 Correct 5 ms 33372 KB Output is correct
90 Correct 5 ms 33372 KB Output is correct
91 Correct 5 ms 33372 KB Output is correct
92 Correct 7 ms 33372 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33368 KB Output is correct
2 Correct 5 ms 33372 KB Output is correct
3 Correct 5 ms 33372 KB Output is correct
4 Correct 5 ms 33372 KB Output is correct
5 Correct 5 ms 33372 KB Output is correct
6 Correct 5 ms 33372 KB Output is correct
7 Correct 5 ms 33372 KB Output is correct
8 Correct 5 ms 33244 KB Output is correct
9 Correct 5 ms 33372 KB Output is correct
10 Correct 5 ms 33372 KB Output is correct
11 Correct 5 ms 33372 KB Output is correct
12 Correct 5 ms 33236 KB Output is correct
13 Correct 5 ms 33372 KB Output is correct
14 Correct 5 ms 33372 KB Output is correct
15 Correct 5 ms 33372 KB Output is correct
16 Correct 5 ms 33372 KB Output is correct
17 Correct 5 ms 33424 KB Output is correct
18 Correct 5 ms 33372 KB Output is correct
19 Correct 5 ms 33416 KB Output is correct
20 Correct 5 ms 33372 KB Output is correct
21 Correct 5 ms 33468 KB Output is correct
22 Correct 5 ms 33480 KB Output is correct
23 Correct 5 ms 33240 KB Output is correct
24 Correct 5 ms 33372 KB Output is correct
25 Correct 5 ms 33460 KB Output is correct
26 Correct 5 ms 33236 KB Output is correct
27 Correct 5 ms 33372 KB Output is correct
28 Correct 5 ms 33372 KB Output is correct
29 Correct 5 ms 33372 KB Output is correct
30 Correct 5 ms 33372 KB Output is correct
31 Correct 5 ms 33420 KB Output is correct
32 Correct 5 ms 33476 KB Output is correct
33 Correct 5 ms 33368 KB Output is correct
34 Correct 6 ms 33372 KB Output is correct
35 Correct 5 ms 33372 KB Output is correct
36 Correct 5 ms 33372 KB Output is correct
37 Correct 5 ms 33464 KB Output is correct
38 Correct 6 ms 33372 KB Output is correct
39 Correct 5 ms 33372 KB Output is correct
40 Correct 6 ms 33372 KB Output is correct
41 Correct 5 ms 33424 KB Output is correct
42 Correct 5 ms 33472 KB Output is correct
43 Correct 5 ms 33372 KB Output is correct
44 Correct 5 ms 33476 KB Output is correct
45 Correct 5 ms 33368 KB Output is correct
46 Correct 5 ms 33372 KB Output is correct
47 Correct 5 ms 33368 KB Output is correct
48 Correct 5 ms 33372 KB Output is correct
49 Correct 6 ms 33372 KB Output is correct
50 Correct 5 ms 33368 KB Output is correct
51 Correct 5 ms 33476 KB Output is correct
52 Correct 5 ms 33372 KB Output is correct
53 Correct 6 ms 33368 KB Output is correct
54 Correct 5 ms 33372 KB Output is correct
55 Correct 5 ms 33372 KB Output is correct
56 Correct 5 ms 33372 KB Output is correct
57 Correct 5 ms 33372 KB Output is correct
58 Correct 5 ms 33372 KB Output is correct
59 Correct 5 ms 33236 KB Output is correct
60 Correct 5 ms 33372 KB Output is correct
61 Correct 5 ms 33372 KB Output is correct
62 Correct 6 ms 33372 KB Output is correct
63 Correct 5 ms 33416 KB Output is correct
64 Correct 6 ms 33372 KB Output is correct
65 Correct 6 ms 33372 KB Output is correct
66 Incorrect 82 ms 56992 KB Output isn't correct
67 Halted 0 ms 0 KB -