oj.uz

Submission #171016

# Submission time Handle Problem Language Result Execution time Memory
171016 2019-12-27T05:03:32 Z juggernaut Shymbulak (IZhO14_shymbulak) C++14
50 / 100
 874 ms 1016 KB 
//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
vector<vector<int>>g(5001);
int a[5001],n,x,y,i,j,mx,cnt,b[5001];
main(){
    scanf("%lld",&n);
    for(i=0;i<n;i++){
        scanf("%lld%lld",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1;i<=n;i++){
        queue<int>q;
        q.push(i);
        for(j=1;j<=n;j++)a[j]=1e15,b[j]=0;
        b[i]=1;
        a[i]=0;
        while(!q.empty()){
            x=q.front();
            q.pop();
            for(int to:g[x])
            if(a[to]>a[x]+1){
                b[to]+=b[x];
                a[to]=a[x]+1;
                q.push(to);
            }else if(a[to]==a[x]+1)b[to]+=b[x];
        }
        for(j=1;j<=n;j++)
        if(a[j]>mx){
            mx=a[j];
            cnt=b[j];
        }else if(mx==a[j])cnt+=b[j];
    }
    printf("%lld",(cnt>>1));
}

Compilation message

shymbulak.cpp:7:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
shymbulak.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 3 ms 380 KB Output is correct
14 Correct 9 ms 504 KB Output is correct
15 Correct 7 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 504 KB Output is correct
2 Correct 10 ms 504 KB Output is correct
3 Correct 23 ms 632 KB Output is correct
4 Correct 22 ms 540 KB Output is correct
5 Correct 673 ms 788 KB Output is correct
6 Correct 368 ms 760 KB Output is correct
7 Correct 874 ms 888 KB Output is correct
8 Correct 776 ms 1016 KB Output is correct
9 Correct 621 ms 892 KB Output is correct
10 Correct 735 ms 760 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -