제출 #211984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211984		eriksuenderhauf	조이터에서 친구를 만드는건 재밌어 (JOI20_joitter2)	C++11	100 / 100	1154 ms	191552 KiB

joitter2

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define trav(x,a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int _i = 1; _i <= (n); _i++) ni(a[_i])
#define nal(a, n) for (int _i = 1; _i <= (n); _i++) nl(a[_i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
const double eps = 1e-9;

int par[N];
set<int> eIn[N], eOut[N], comp[N];
ll ans, sz[N];

int qry(int x) { return x == par[x] ? x : par[x] = qry(par[x]); }
void upd(int u, int f) { ans += f * sz[u] * 1ll * (sz(comp[u]) - 1); }

deque<pii> pq;

void join(int u, int v) {
  {
    if (eIn[u].count(v))
      eIn[u].erase(eIn[u].find(v));
    if (eIn[v].count(u))
      eIn[v].erase(eIn[v].find(u));
    if (eOut[u].count(v))
      eOut[u].erase(eOut[u].find(v));
    if (eOut[v].count(u))
      eOut[v].erase(eOut[v].find(u));
  }
  if (sz(comp[u]) > sz(comp[v]))
    swap(u, v);
  par[u] = v;
  sz[v] += sz[u];
  trav(x, comp[u]) comp[v].insert(x);
  trav(x, eIn[u]) {
    if (eOut[v].count(x))
      pq.pb({x, v});
    eOut[x].erase(eOut[x].find(u));
    eOut[x].insert(v);
    eIn[v].insert(x);
  }
  trav(x, eOut[u]) {
    if (eIn[v].count(x))
      pq.pb({x, v});
    eIn[x].erase(eIn[x].find(u));
    eIn[x].insert(v);
    eOut[v].insert(x);
  }
  eIn[u].clear();
  eOut[u].clear();
  comp[u].clear();
}

int main() {
  int n, m; scanf("%d %d", &n, &m);
  iota(par, par+n+1, 0);
  fill(sz, sz+n+1, 1);
  for (int i = 1; i <= n ; i++)
    comp[i].insert(i);
  while (m--) {
    int u, v; scanf("%d %d", &u, &v);
    if (eOut[qry(v)].count(qry(u))) {
      pq.pb({u, v});
      while (!pq.empty()) {
        tie(u, v) = pq.front();
        pq.pop_front();
        if (qry(u) == qry(v))
          continue;
        upd(qry(u), -1);
        upd(qry(v), -1);
        join(qry(u), qry(v));
        upd(qry(u), 1);
      }
    } else if (qry(u) != qry(v)) {
      upd(qry(v), -1);
      comp[qry(v)].insert(u);
      eIn[qry(v)].insert(qry(u));
      eOut[qry(u)].insert(qry(v));
      upd(qry(v), 1);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joitter2.cpp: In function 'int main()':
joitter2.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int n, m; scanf("%d %d", &n, &m);
             ~~~~~^~~~~~~~~~~~~~~~~
joitter2.cpp:88:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int u, v; scanf("%d %d", &u, &v);
               ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 16 / 16
• Subtask 3: 83 / 83