Submission #345454

#	Time	Username	Problem	Language	Result	Execution time	Memory
345454		impri	산만한 고양이 (KOI17_cat)	C++14	100 / 100	532 ms	50048 KiB

cat

#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(num[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;
}
cout << result;
}

Compilation message (stderr)

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;
      |        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 55 / 55