| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 887165 | 2023-12-13T23:10:34 Z | Servant_of_the_Lord | Sirni (COCI17_sirni) | C++17 | 2619 ms | 607836 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse4")
#define ll long long
using namespace std;
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
ll x,y,z,a,b,c;
cin>>x;
set<pair<ll,ll>>s;
for(ll i=0;i<x;i++)
{
cin>>y;
s.insert({y,i});
}
vector<vector<ll>>v(10'000'000);
for(pair<ll,ll> i:s)
{
if(v[i.first-1].empty())
{
for(ll j=i.first-1;j<10'000'000;j+=i.first)
{
v[j].push_back(i.second);
}
}
}
vector<ll>w(x,-1);
function<ll(ll)>g=[&](ll a){return w[a]<0?a:w[a]=g(w[a]);};
y=x;
function<bool(ll,ll)>u=[&](ll a,ll b)
{
a=g(a),b=g(b);
if(a==b)return false;
if(w[a]>w[b])swap(a,b);
w[a]+=w[b];
w[b]=a;
y--;
return true;
};
a=0;
bitset<10'000'000>t;
for(ll i=0;i<10'000'000;i++)
{
vector<pair<ll,ll>>e;
for(pair<ll,ll> j:s)
{
for(ll k=0;k<v[j.first-i-1].size();k++)
{
if(u(j.second,v[j.first-i-1][k]))
{
a+=i;
}
}
if(j.first-i-1==0||t[j.first-i-1])e.push_back(j);
t[j.first-i-1]=1;
}
for(auto j:e)s.erase(j);
if(s.empty()||y==1)break;
}
cout<<a<<'\n';
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 214 ms | 236628 KB | Output is correct |
| 2 | Correct | 526 ms | 299344 KB | Output is correct |
| 3 | Correct | 99 ms | 237136 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 678 ms | 372304 KB | Output is correct |
| 2 | Correct | 1508 ms | 583588 KB | Output is correct |
| 3 | Correct | 66 ms | 238412 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 209 ms | 236624 KB | Output is correct |
| 2 | Correct | 86 ms | 236396 KB | Output is correct |
| 3 | Correct | 136 ms | 236704 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1457 ms | 403780 KB | Output is correct |
| 2 | Correct | 2343 ms | 546048 KB | Output is correct |
| 3 | Correct | 2339 ms | 593040 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 303 ms | 284336 KB | Output is correct |
| 2 | Correct | 2132 ms | 435900 KB | Output is correct |
| 3 | Correct | 2173 ms | 504572 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2244 ms | 471632 KB | Output is correct |
| 2 | Correct | 2211 ms | 607836 KB | Output is correct |
| 3 | Correct | 1398 ms | 499452 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1599 ms | 457000 KB | Output is correct |
| 2 | Correct | 2539 ms | 607580 KB | Output is correct |
| 3 | Correct | 1962 ms | 569912 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 728 ms | 280228 KB | Output is correct |
| 2 | Correct | 1809 ms | 553876 KB | Output is correct |
| 3 | Correct | 741 ms | 291740 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 487 ms | 291976 KB | Output is correct |
| 2 | Correct | 2506 ms | 599908 KB | Output is correct |
| 3 | Correct | 702 ms | 442392 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 307 ms | 243540 KB | Output is correct |
| 2 | Correct | 2619 ms | 502936 KB | Output is correct |
| 3 | Correct | 2128 ms | 578436 KB | Output is correct |