| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 887142 | 2023-12-13T21:29:02 Z | Servant_of_the_Lord | Sirni (COCI17_sirni) | C++17 | 5000 ms | 611472 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#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<ll>s;
map<ll,ll>m;
for(ll i=0;i<x;i++)
{
cin>>y;
s.insert(y);
m[y]=i;
}
vector<vector<ll>>v(10'000'000);
for(ll i:s)
{
if(v[i-1].empty())
{
for(ll j=i-1;j<10'000'000;j+=i)
{
v[j].push_back(i);
}
}
}
vector<ll>w(x,-1);
function<ll(ll)>g=[&](ll a){return w[a]<0?a:w[a]=g(w[a]);};
function<bool(ll,ll)>u=[&](ll a,ll b)
{
a=g(m[a]),b=g(m[b]);
if(a==b)return false;
if(w[a]>w[b])swap(a,b);
w[a]+=w[b];
w[b]=a;
return true;
};
a=0;
bitset<10'000'000>t;
for(ll i=0;i<10'000'000;i++)
{
vector<ll>e;
for(ll j:s)
{
for(ll k:v[j-i-1])
{
if(u(j,k))
{
a+=i;
}
}
if(j-i-1==0||t[j-i-1])e.push_back(j);
t[j-i-1]=1;
}
for(ll j:e)s.erase(j);
if(s.empty())break;
}
cout<<a<<'\n';
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 576 ms | 236576 KB | Output is correct |
| 2 | Correct | 1597 ms | 299360 KB | Output is correct |
| 3 | Correct | 555 ms | 237140 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 693 ms | 372304 KB | Output is correct |
| 2 | Correct | 4083 ms | 583708 KB | Output is correct |
| 3 | Correct | 629 ms | 238420 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 568 ms | 236628 KB | Output is correct |
| 2 | Correct | 316 ms | 236436 KB | Output is correct |
| 3 | Correct | 559 ms | 236884 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1733 ms | 407872 KB | Output is correct |
| 2 | Correct | 2716 ms | 549272 KB | Output is correct |
| 3 | Correct | 2819 ms | 594960 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 392 ms | 284896 KB | Output is correct |
| 2 | Correct | 2446 ms | 428628 KB | Output is correct |
| 3 | Correct | 2365 ms | 507368 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2638 ms | 475496 KB | Output is correct |
| 2 | Correct | 2744 ms | 611472 KB | Output is correct |
| 3 | Correct | 1880 ms | 503140 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1660 ms | 458220 KB | Output is correct |
| 2 | Correct | 3082 ms | 608736 KB | Output is correct |
| 3 | Correct | 2479 ms | 572152 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2517 ms | 284628 KB | Output is correct |
| 2 | Execution timed out | 5087 ms | 558388 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2300 ms | 296528 KB | Output is correct |
| 2 | Execution timed out | 5084 ms | 602320 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 803 ms | 244504 KB | Output is correct |
| 2 | Execution timed out | 5034 ms | 503912 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |