oj.uz

Submission #557985

# Submission time Handle Problem Language Result Execution time Memory
557985 2022-05-06T12:28:55 Z 600Mihnea Making Friends on Joitter is Fun (JOI20_joitter2) C++17
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>

bool home = 1;

using namespace std;

typedef long long ll;

const int N=(int)1e5+7;
int n;
int m;
int t[N];
int sz[N];
ll sol=0;
set<int> g[N];

int root(int a) {
  if (t[a]==a) return a;
  return t[a]=root(t[a]);
}


ll contrib(int i) {
  i=root(i);
  return ((ll)g[i].size()-1)*(ll)sz[i];
}

void join(int a,int b){
  a=root(a);
  b=root(b);

  if(a==b) {
    return;
  }

  if ((int)g[a].size()>(int)g[b].size()) swap(a, b);

  sol-=contrib(a);
  sol-=contrib(b);


  for (auto &j:g[a]) {
    g[b].insert(j);
  }


  t[a]=b;

  g[a].clear();
  sz[b]+=sz[a];

  sol+=contrib(b);
}

signed main() {
#ifdef ONLINE_JUDGE
  home = 0;
#endif

  home=0;

  if (home) {
    freopen("I_am_iron_man", "r", stdin);
  }
  else {
    ios::sync_with_stdio(0); cin.tie(0);
  }

  cin>>n>>m;
  for (int i=1;i<=n;i++) {
    t[i]=i;
    sz[i]=1;
    g[i]={i};
  }
  vector<pair<int, int>> edges;

  for (int i=1;i<=m;i++) {
    int a,b;
    cin>>a>>b;

    sol-=contrib(b);
    g[root(b)].insert(a);
    sol+=contrib(b);

    edges.push_back({a, b});
    bool is=0;
    for (auto &it:edges){
      if(root(it.first)==root(b)&&root(it.second)==root(a)) {
        is=1;
      }
    }
    if (is) {
      join(a, b);
    }

    cout<<sol<<"\n";
  }

}

Compilation message

joitter2.cpp: In function 'int main()':
joitter2.cpp:63:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     freopen("I_am_iron_man", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 83.0

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