oj.uz

Submission #345440

# Submission time Handle Problem Language Result Execution time Memory
345440 2021-01-07T10:25:33 Z impri None (KOI17_cat) C++14
33 / 100
 459 ms 47084 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>graph[300001];
int num[300001];
int low[300001];
int visited[300001];
int parent[300001];
int res[300001];
int cnt=1;
int rnum=0;
void v(int c){
num[c]=cnt;
low[c]=cnt;
visited[c]=1;
cnt++;
for(int i=0;i<graph[c].size();i++){
    int nxt=graph[c][i];
    if(!visited[nxt]){
       if(c==1)
        rnum++;
        parent[nxt]=c;
        v(nxt);
        if(low[nxt]>=num[c]){
            res[c]++;
        }
        low[c]=min(low[nxt], low[c]);
    }
    else{
        if(nxt!=parent[c]){
            low[c]=min(low[nxt],low[c]);
        }
    }
}


}
int main(void){
cin >> n >> m;
for(int i=2;i<=n;i++)res[i]=1;
for(int i=1;i<=m;i++){
    int a,b;
    cin >> a >> b;
   graph[b].push_back(a); graph[a].push_back(b);
}
v(1);
long long result=0;
if(m-graph[1].size()==n-1-rnum)result+=1;
for(int i=2;i<=n;i++){
    if(m-graph[i].size()==n-1-res[i])result+=i*1LL;
}
cout << result;
}

Compilation message

cat.cpp: In function 'void v(int)':
cat.cpp:17:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | for(int i=0;i<graph[c].size();i++){
      |             ~^~~~~~~~~~~~~~~~
cat.cpp:20:8: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |        if(c==1)
      |        ^~
cat.cpp:22:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |         parent[nxt]=c;
      |         ^~~~~~
cat.cpp: In function 'int main()':
cat.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 | if(m-graph[1].size()==n-1-rnum)result+=1;
      |    ~~~~~~~~~~~~~~~~~^~~~~~~~~~
cat.cpp:50:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if(m-graph[i].size()==n-1-res[i])result+=i*1LL;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Incorrect 5 ms 7404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 23868 KB Output is correct
2 Correct 412 ms 23848 KB Output is correct
3 Correct 408 ms 24044 KB Output is correct
4 Correct 406 ms 23788 KB Output is correct
5 Correct 426 ms 23916 KB Output is correct
6 Correct 435 ms 24044 KB Output is correct
7 Correct 438 ms 23920 KB Output is correct
8 Correct 459 ms 23856 KB Output is correct
9 Correct 422 ms 24028 KB Output is correct
10 Correct 452 ms 23972 KB Output is correct
11 Correct 411 ms 24516 KB Output is correct
12 Correct 435 ms 24384 KB Output is correct
13 Correct 429 ms 24312 KB Output is correct
14 Correct 423 ms 24500 KB Output is correct
15 Correct 415 ms 24428 KB Output is correct
16 Correct 419 ms 28908 KB Output is correct
17 Correct 425 ms 30060 KB Output is correct
18 Correct 407 ms 27884 KB Output is correct
19 Correct 417 ms 28908 KB Output is correct
20 Correct 430 ms 27908 KB Output is correct
21 Correct 431 ms 26340 KB Output is correct
22 Correct 409 ms 35052 KB Output is correct
23 Correct 378 ms 37996 KB Output is correct
24 Correct 435 ms 26620 KB Output is correct
25 Correct 396 ms 36844 KB Output is correct
26 Correct 271 ms 47084 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 46948 KB Output is correct
2 Correct 258 ms 47084 KB Output is correct
3 Correct 251 ms 46956 KB Output is correct
4 Correct 255 ms 47004 KB Output is correct
5 Correct 245 ms 46956 KB Output is correct
6 Correct 247 ms 46992 KB Output is correct
7 Correct 257 ms 46932 KB Output is correct
8 Correct 262 ms 46992 KB Output is correct
9 Correct 252 ms 47016 KB Output is correct
10 Correct 283 ms 40828 KB Output is correct
11 Correct 287 ms 40936 KB Output is correct
12 Correct 280 ms 40860 KB Output is correct
13 Correct 267 ms 40936 KB Output is correct
14 Correct 291 ms 40400 KB Output is correct
15 Correct 309 ms 34152 KB Output is correct
16 Correct 273 ms 34148 KB Output is correct
17 Correct 347 ms 34148 KB Output is correct
18 Correct 348 ms 34148 KB Output is correct
19 Correct 307 ms 34148 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Incorrect 5 ms 7404 KB Output isn't correct
4 Halted 0 ms 0 KB -