Submission #10443247


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

const int MAX_N = 112345;
vector<int> g[MAX_N], hate[MAX_N];
int ans[MAX_N];
bool vis[MAX_N];


void dfs(int cur, vector<int>& out) {
  if (vis[cur]) return;
  vis[cur] = true;
  out.push_back(cur);
  for (int nxt : g[cur]) if (!vis[nxt]) {
    dfs(nxt, out);
  }
}

int main2() {
  CLR(ans, 0);
  CLR(vis, 0);
  REP(i, MAX_N) g[i].clear();
  REP(i, MAX_N) hate[i].clear();
  int N = nextInt();
  int M = nextInt();
  int K = nextInt();

  REP(i, M) {
    int a = nextInt() - 1;
    int b = nextInt() - 1;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  REP(i, K) {
    int a = nextInt() - 1;
    int b = nextInt() - 1;
    hate[a].push_back(b);
    hate[b].push_back(a);
  }

  REP(i, N) if (!vis[i]) {
    vector<int> out;
    dfs(i, out);
    set<int> st(ALL(out));
    for (int x : out) {
      int val = out.size();
      val--;
      val -= g[x].size();
      for (int y : hate[x]) {
        if (st.count(y)) val--;
      }
      ans[x] = val;
    }
  }

  REP(i, N) {
    if (i > 0) printf(" ");
    printf("%d", ans[i]);
  }
  printf("\n");

  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Submission Info

Submission Time
Task D - Friend Suggestions
User hs484
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1783 Byte
Status AC
Exec Time 172 ms
Memory 17648 KB

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:14:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int nextInt() { int x; scanf("%d", &x); return x;}
                                       ^
./Main.cpp: In function ‘ll nextLong()’:
./Main.cpp:15:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll nextLong() { ll x; scanf("%lld", &x); return x;}
                                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 30
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 02-small-00, 02-small-01, 02-small-02, 02-small-03, 02-small-04, 02-small-05, 02-small-06, 02-small-07, 02-small-08, 02-small-09, 03-large-00, 03-large-01, 03-large-02, 03-large-03, 03-large-04, 03-large-05, 03-large-06, 03-large-07, 03-large-08, 03-large-09
Case Name Status Exec Time Memory
00-sample-00 AC 4 ms 6016 KB
00-sample-01 AC 4 ms 6016 KB
00-sample-02 AC 4 ms 6016 KB
01-handmade-00 AC 4 ms 6016 KB
01-handmade-01 AC 4 ms 6016 KB
01-handmade-02 AC 52 ms 11816 KB
01-handmade-03 AC 36 ms 7936 KB
01-handmade-04 AC 172 ms 17268 KB
01-handmade-05 AC 169 ms 17648 KB
01-handmade-06 AC 74 ms 9088 KB
02-small-00 AC 4 ms 6016 KB
02-small-01 AC 4 ms 6016 KB
02-small-02 AC 4 ms 6016 KB
02-small-03 AC 4 ms 6016 KB
02-small-04 AC 4 ms 6016 KB
02-small-05 AC 4 ms 6016 KB
02-small-06 AC 4 ms 6016 KB
02-small-07 AC 4 ms 6016 KB
02-small-08 AC 4 ms 6016 KB
02-small-09 AC 4 ms 6016 KB
03-large-00 AC 109 ms 12796 KB
03-large-01 AC 120 ms 14972 KB
03-large-02 AC 105 ms 13856 KB
03-large-03 AC 98 ms 13308 KB
03-large-04 AC 101 ms 13484 KB
03-large-05 AC 105 ms 13312 KB
03-large-06 AC 97 ms 12288 KB
03-large-07 AC 118 ms 13860 KB
03-large-08 AC 134 ms 15736 KB
03-large-09 AC 152 ms 17092 KB