結果
| 問題 | No.1509 Swap!! |
| ユーザー |
 rukorukoru@下の若作り
|
| 提出日時 | 2023-07-22 03:10:18 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,660 bytes |
| コンパイル時間 | 5,026 ms |
| コンパイル使用メモリ | 279,912 KB |
| 実行使用メモリ | 8,804 KB |
| 最終ジャッジ日時 | 2024-09-22 04:16:29 |
| 合計ジャッジ時間 | 10,633 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | WA | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
| testcase_28 | RE | - |
| testcase_29 | RE | - |
| testcase_30 | RE | - |
ソースコード
#include<bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
const int mod = 998244353;
const long long modx = 1000000007;
using mint = modint998244353;
using mint1 = modint1000000007;
typedef long long ll;
template <class T> using V = vector<T>;
#define fore(i,a) for(auto &i:a)
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
#define ALL(a) (a).begin(),(a).end()
#define rep(i, l, r) for(ll i = (ll)(l); i < (ll)(r); ++i)
#define rev(i, l, r) for(ll i = (ll)(l); i >= (ll)(r); --i)
#define IN(nx,ny,h,w) (nx >= 0 && nx < h && ny >= 0 && ny < w)
template<typename T> inline bool chmin(T& a, T b) { return (a > b) ? (a = b, true) : false; }
template<typename T> inline bool chmax(T& a, T b) { return (a < b) ? (a = b, true) : false; }
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
vector<ll> dx = {0,1,-1,0};
vector<ll> dy = {-1,0,0,1};
int ketasu(ll N){
int digits=0;
while(N>0){
N/=10;
digits++;
}
return digits;
}
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
std::vector<int> Eratosthenes( const int N )
{
std::vector<bool> is_prime( N + 1 );
for( int i = 0; i <= N; i++ )
{
is_prime[ i ] = true;
}
std::vector<int> P;
for( int i = 2; i <= N; i++ )
{
if( is_prime[ i ] )
{
for( int j = 2 * i; j <= N; j += i )
{
is_prime[ j ] = false;
}
P.emplace_back( i );
}
}
return P;
}
string toBinary(ll n)
{
string r;
while (n != 0){
r += ( n % 2 == 0 ? "0" : "1" );
n /= 2;
}
return r;
}
vector<bool> seen;
using Graph = vector<vector<ll>>;
void dfs(const Graph &G, ll v){
seen[v] = true;
for(auto next_v : G[v]){
if(seen[next_v]) continue;
dfs(G,next_v);
}
}
ll kewa(ll n){
ll ans =0;
while(n>0){
ans += n%10;
n /= 10;
}
return ans;
}
vector<ll> ke(ll n){
vector<ll> a;
while(n>0){
a.push_back(n%10);
n /= 10;
}
reverse(a.begin(),a.end());
return a;
}
long long powll(long long x, long long n, ll amari) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % amari; // n の最下位bitが 1 ならば x^(2^i) をかける
x = x * x % amari;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
ll target;
bool fseg(ll v){return v < target;}
ll string_mod(string s, ll mod){
ll rest = 0;
for(char c : s){
ll v = c-'0';
rest = (rest*10 + v) % mod;
}
return rest;
}
template< unsigned mod >
struct RollingHash {
vector< unsigned > hashed, power;
inline unsigned mul(unsigned a, unsigned b) const {
unsigned long long x = (unsigned long long) a * b;
unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod));
return m;
}
RollingHash(const string &s, unsigned base = 10007) {
int sz = (int) s.size();
hashed.assign(sz + 1, 0);
power.assign(sz + 1, 0);
power[0] = 1;
for(int i = 0; i < sz; i++) {
power[i + 1] = mul(power[i], base);
hashed[i + 1] = mul(hashed[i], base) + s[i];
if(hashed[i + 1] >= mod) hashed[i + 1] -= mod;
}
}
unsigned get(int l, int r) const {
unsigned ret = hashed[r] + mod - mul(hashed[l], power[r - l]);
if(ret >= mod) ret -= mod;
return ret;
}
unsigned connect(unsigned h1, int h2, int h2len) const {
unsigned ret = mul(h1, power[h2len]) + h2;
if(ret >= mod) ret -= mod;
return ret;
}
int LCP(const RollingHash< mod > &b, int l1, int r1, int l2, int r2) {
int len = min(r1 - l1, r2 - l2);
int low = -1, high = len + 1;
while(high - low > 1) {
int mid = (low + high) / 2;
if(get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid;
else high = mid;
}
return (low);
}
};
ll op(ll a,ll b){
return min(a,b);
}
ll e(){
return (int)(1e18);
}
using RH = RollingHash< 1000000007 >;
#ifdef _MSC_VER
inline unsigned int __builtin_popcount(unsigned int x) { return __popcnt(x); }
#endif // _MSC_VER
#define def 0
template<class V, int NV> struct SegTree { //[l,r)
V comp(V& l, V& r) { return l | r; };
vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
V get(int x, int y, int l = 0, int r = NV, int k = 1) {
if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
auto a = get(x, y, l, (l + r) / 2, k * 2);
auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
return comp(a, b);
}
void update(int i, V v) {
i += NV; val[i] = v;
while (i>1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
}
void add(int i, V v) { update(i, val[i + NV] + v); }
V operator[](int x) { return get(x, x + 1); }
};
ll MOD = 1000000007;
long long pow_mod(long long x, long long n) {
long long ret = 1;
while (n > 0) {
if (n & 1) ret = ret * x % MOD; // n の最下位bitが1ならば(nが奇数ならば) x^(2^i) をかける
x = x * x % MOD;
n >>= 1; // n を1bit 左にずらす
}
return ret;
}
long long nCr_mod(long long n, long long r) {
long long x = 1, y = 1;
for (int i = 0; i < r; i++) {
x = x * (n - i) % MOD ;
y = y * (i + 1) % MOD;
}
return x * pow_mod(y, MOD - 2) % MOD;
}
vector<long long> divisor(long long n) {
vector<long long> ret;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(ret.begin(), ret.end()); // 昇順に並べる
return ret;
}
bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; // 偶数はあらかじめ除く
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
// 素数ではない
return false;
}
}
// 素数である
return true;
}
template <bool Strict, class Type>
size_t LIS(const std::vector<Type>& v)
{
std::vector<Type> dp;
auto it = dp.begin();
for (const auto& elem : v)
{
if constexpr (Strict)
{
it = std::lower_bound(dp.begin(), dp.end(), elem);
}
else
{
it = std::upper_bound(dp.begin(), dp.end(), elem);
}
if (it == dp.end())
{
dp.push_back(elem);
}
else
{
*it = elem;
}
}
return dp.size();
}
string Binary(ll n)
{
string r;
while (n != 0){
r += ( n % 2 == 0 ? "0" : "1" );
n /= 2;
}
return r;
}
template <class Type>
size_t LIS(const std::vector<Type>& v)
{
std::vector<Type> dp;
for (const auto& elem : v)
{
auto it = std::lower_bound(dp.begin(), dp.end(), elem);
if (it == dp.end())
{
dp.push_back(elem);
}
else
{
*it = elem;
}
}
return dp.size();
}
vector<pair<ll,ll>> edge[200005];
vector<pair<ll,pair<ll,ll>>> g;
int main() {
ll n,m;
cin >> n >> m;
vector<ll> a(n),b(n);
rep(i,0,n) cin >> a[i];
rep(i,0,n) cin >> b[i];
rep(i,0,m){
ll x,y,z;
cin >> x >> y >> z;
x--;y--;
edge[x].push_back({y,z});
edge[y].push_back({x,z});
g.push_back({z,{x,y}});
}
sort(ALL(g));
dsu uf(n);
ll sum = 0;
vector<pair<ll,pair<ll,ll>>> m1;
rep(i,0,m){
ll x = g[i].second.first;
ll y = g[i].second.second;
ll z = g[i].first;
if(uf.same(x,y) == false){
sum += z;
uf.merge(x,y);
m1.push_back({z,{x,y}});
}
}
reverse(ALL(m1));
}