oj.uz

답안 #120725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120725 2019-06-25T10:36:20 Z _demon_ 철인 이종 경기 (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n,m;
    ll child[100009];
    ll ans;
    ll w[100009];
    vector<ll>v[100009];
    int done[100009];
    int comp[100009];
    int mp[1000009];
    int crnt=0;
    void dfs1(int node,int p){
        child[node]=1;
        done[node]=1;
        comp[node]=crnt;
        mp[crnt]++;
        if(node!=p)w[node]=w[p]+1;
        for(int i=0;i<v[node].size();i++){
            int u=v[node][i];
            if(u==p)continue;
            dfs1(u,node);
            child[node]+=child[u];
        }
    }
    int a[100009];
    void dfs2(int node,int p){
        done[node]=1;
        ll sum=0;
        for(int i=0;i<v[node].size();i++){
            int u=v[node][i];
            if(w[u]>w[node]){
                sum+=child[u]*(mp[comp[node]]-child[u]-1);
            }
            else{
                sum+=(mp[comp[node]]-child[node])*(child[node]-1);
            }
        }
        a[node]=sum;
        ans+=sum;
        for(int i=0;i<v[node].size();i++){
            int u=v[node][i];
            if(u==p)continue;
            dfs2(u,node);
        }
    }
    int main(){
        cin>>n>>m;
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            a--;b--;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        for(int i=0;i<n;i++){
            if(done[i]==0){
                dfs1(i,i);
                crnt++;
            }
        }
        memset(done,0,sizeof(done));
        for(int i=0;i<n;i++){
            if(done[i]==0){
              dfs2(i,i);
            }
        }
    /*  for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
    cout<<endl;*/
        cout<<ans<<endl;
    }

Compilation message

count_triplets.cpp: In function 'void dfs1(int, int)':
count_triplets.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[node].size();i++){
                     ~^~~~~~~~~~~~~~~
count_triplets.cpp: In function 'void dfs2(int, int)':
count_triplets.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[node].size();i++){
                     ~^~~~~~~~~~~~~~~
count_triplets.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[node].size();i++){
                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 789 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 789 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 224000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3200 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Correct 5 ms 3200 KB Output is correct
4 Correct 4 ms 3200 KB Output is correct
5 Correct 5 ms 3116 KB Output is correct
6 Correct 5 ms 3200 KB Output is correct
7 Correct 5 ms 3200 KB Output is correct
8 Correct 4 ms 3200 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 5 ms 3200 KB Output is correct
11 Correct 5 ms 3220 KB Output is correct
12 Correct 5 ms 3200 KB Output is correct
13 Correct 5 ms 3200 KB Output is correct
14 Correct 5 ms 3200 KB Output is correct
15 Correct 12 ms 3200 KB Output is correct
16 Correct 5 ms 3072 KB Output is correct
17 Correct 8 ms 3200 KB Output is correct
18 Correct 4 ms 3200 KB Output is correct
19 Correct 5 ms 3200 KB Output is correct
20 Correct 5 ms 3200 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 9128 KB Output is correct
2 Correct 140 ms 9300 KB Output is correct
3 Correct 144 ms 9148 KB Output is correct
4 Correct 129 ms 9180 KB Output is correct
5 Correct 128 ms 9204 KB Output is correct
6 Correct 154 ms 12156 KB Output is correct
7 Correct 157 ms 11464 KB Output is correct
8 Correct 147 ms 10844 KB Output is correct
9 Correct 140 ms 10108 KB Output is correct
10 Correct 134 ms 9124 KB Output is correct
11 Correct 137 ms 10564 KB Output is correct
12 Correct 131 ms 10460 KB Output is correct
13 Correct 119 ms 10488 KB Output is correct
14 Correct 103 ms 10104 KB Output is correct
15 Correct 99 ms 9816 KB Output is correct
16 Correct 67 ms 8696 KB Output is correct
17 Correct 95 ms 10600 KB Output is correct
18 Correct 98 ms 10696 KB Output is correct
19 Correct 102 ms 10620 KB Output is correct
20 Correct 96 ms 10600 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3072 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Runtime error 898 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 9208 KB Output is correct
2 Correct 147 ms 9080 KB Output is correct
3 Execution timed out 1148 ms 1008692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 789 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 789 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -