#901885 (C++14) No.2418 情報通だよ！Nafmoくん

提出ソース

結果

問題	No.2418 情報通だよ！Nafmoくん
ユーザー	bluebery1001
提出日時	2023-08-12 13:43:26
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	71 ms / 2,000 ms
コード長	5,646 bytes
コンパイル時間	5,600 ms
コンパイル使用メモリ	271,980 KB
実行使用メモリ	11,008 KB
最終ジャッジ日時	2024-11-14 12:21:10
合計ジャッジ時間	7,106 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	67 ms 8,704 KB
testcase_04	AC	51 ms 10,112 KB
testcase_05	AC	19 ms 6,816 KB
testcase_06	AC	58 ms 9,216 KB
testcase_07	AC	18 ms 6,820 KB
testcase_08	AC	71 ms 11,008 KB
testcase_09	AC	25 ms 6,816 KB
testcase_10	AC	59 ms 7,680 KB
testcase_11	AC	54 ms 7,680 KB
testcase_12	AC	43 ms 7,168 KB
testcase_13	AC	15 ms 6,816 KB
testcase_14	AC	30 ms 6,816 KB
testcase_15	AC	13 ms 6,820 KB
testcase_16	AC	35 ms 6,820 KB
testcase_17	AC	7 ms 6,820 KB
testcase_18	AC	45 ms 8,448 KB
testcase_19	AC	54 ms 9,472 KB
testcase_20	AC	14 ms 6,816 KB
testcase_21	AC	21 ms 6,816 KB
testcase_22	AC	9 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'void print(const T&, const Ts& ...)':
main.cpp:39:36: warning: fold-expressions only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   39 |     (cout << ... << (cout << ' ', b));
      |                                    ^
main.cpp: In function 'll zaatu(std::vector<long long int>&)':
main.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   81 |     for(auto&&[key,val]:m)val=ret++;
      |               ^

ソースコード

raw source code

using namespace std;
#include<bits/stdc++.h>
void _main();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);_main();return 0;}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;typedef long double ld;template<class ll>inline bool chmax(ll&a,ll b){if(a<b){a=b;return 1;}return 0;}template<class ll>inline bool chmin(ll& a,ll b){if(a>b){a=b;return 1;}return 0;}
#define rep1(a)          for(int i = 0; i < a; i++)
#define rep2(i, a)       for(int i = 0; i < a; i++)
#define rep3(i, a, b)    for(int i = a; i < b; i++)
#define rep4(i, a, b, c) for(int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define ALL(x) std::begin(x),std::end(x)
#define INF ((1LL<<62)-(1LL<<31))
#define bit(x,i) (((x)>>(i))&1)
#define fi first
#define se second
#define pb push_back
#define Endl endl
#define spa " "
#define YesNo(x) cout<<(x?"Yes":"No")<<endl;
inline void scan(){}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
template<typename T>
std::istream &operator>>(std::istream&is,std::vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>
std::ostream &operator<<(std::ostream&os,const std::vector<T>&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;}
long double my_distance(long double xi,long double yi,long double xj,long double yj){return sqrt(abs((xi-xj)*(xi-xj))+abs((yi-yj)*(yi-yj)));}
void print(){
    cout << '\n';
}
template<class T, class... Ts>
void print(const T& a, const Ts&... b){
    cout << a;
    (cout << ... << (cout << ' ', b));
    cout << '\n';
}
template<class... T>
constexpr auto min(T... a){
    return min(initializer_list<common_type_t<T...>>{a...});
}
template<class... T>
constexpr auto max(T... a){
    return max(initializer_list<common_type_t<T...>>{a...});
}
//Union-Find from https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/vi((b%2==0?b-1:b)+2-(a%2==0?a+1:a))/2er/union-find
class UnionFind{public:UnionFind()=default;explicit UnionFind(size_t n):m_parentsOrSize(n, -1){}int find(int i){if(m_parentsOrSize[i]<0){return i;}return(m_parentsOrSize[i]=find(m_parentsOrSize[i]));}void merge(int a,int b){a=find(a);b=find(b);if(a!=b){if(-m_parentsOrSize[a]<-m_parentsOrSize[b]){std::swap(a,b);}m_parentsOrSize[a]+=m_parentsOrSize[b];m_parentsOrSize[b]=a;}}bool connected(int a,int b){return (find(a)==find(b));}int size(int i){return -m_parentsOrSize[find(i)];}private:std::vector<int>m_parentsOrSize;};
//ll MOD = INF;
//ll MOD = 1000000007;
ll MOD = 998244353;

bool iskaibun(string s){ll k = s.size();rep(i,0,k/2){if(s[i]!=s[k-1-i]){return false;}}return true;}
#include <atcoder/all>
using namespace atcoder;
string replace(const string&moto,const string &from, const string&too) {
  int from_len = from.size();
  string tmp = from + moto;
  int tmp_len = tmp.size();
  vector<int> za = z_algorithm(tmp);
  string ret = "";
  for (int i = from_len; i < tmp_len;) {
    if (za[i] >= from_len) {
      ret += too;
      i += from_len;
    } else {
      ret += tmp[i];
      i++;
    }
  }
  return ret;
}

ll zaatu(vector<ll>&A){
    map<ll,ll>m;
    for(auto&&x:A)m[x]=0;
    ll ret = 0;
    for(auto&&[key,val]:m)val=ret++;
    for(auto&&x:A)x=m[x];
    return ret;
}
//約数列挙
vector<ll>enumdiv(ll n){
    vector<ll>s;
    for(ll i = 1;i*i<=n;i++){
        if(n%i==0){s.push_back(i);if(i*i!=n)s.push_back(n/i);}
        
    }
    return s;
}
vector<ll> topo_sort(vector<vector<ll>>&G,vector<ll>&nyu_cnt,ll v){
    vector<ll>ret;
    priority_queue<ll,vector<ll>,greater<ll>>pq;
    rep(i,0,v){
        if(nyu_cnt[i]==0)pq.push(i);
    }
    while(!pq.empty()){
        ll pos = pq.top();pq.pop();
        for(ll i:G[pos]){
            nyu_cnt[i]--;
            if(nyu_cnt[i]==0)pq.push(i);
        }
        ret.push_back(pos);
    }
    return ret;
}
vector<pair<ll,ll>> soinsu_bunkai(ll x){
    vector<pair<ll,ll>>ret;
    rep(i,2,sqrt(x)+1){
        if(x%i==0){
            ll cnt{};
            while(x%i==0){
                x/=i;
                cnt++;
            }
            ret.push_back({i,cnt});
        }
    }
    if(x!=1)ret.push_back({x,1});
    return ret;
}

const int MAX = 1010000;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
vector<bool> isprime;
vector<int> Era(int n) {
    isprime.resize(n, true);
    vector<int> res;
    isprime[0] = false; isprime[1] = false;
    for (int i = 2; i < n; ++i) isprime[i] = true;
    for (int i = 2; i < n; ++i) {
        if (isprime[i]) {
            res.push_back(i);
            for (int j = i*2; j < n; j += i) isprime[j] = false;
        }
    }
    return res;
}
using mint = modint998244353;

void _main(){
    LL(n,m);
    UnionFind uf(2*n);
    rep(i,0,m){
        LL(a,b);
        uf.merge(--a,--b);
    }
    set<ll>s;
    ll amari{};
    rep(i,0,2*n){
        if(!s.count(uf.find(i))){
            s.insert(uf.find(i));
            amari += uf.size(i)%2;
        }
    }
    cout<<amari/2<<endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード