oj.uz

답안 #647425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647425 2022-10-02T14:16:08 Z billyisme Sirni (COCI17_sirni) C++14
98 / 140
 2146 ms 786432 KB 
#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define pb push_back
#define pk pop_back
#define pii pair<int,int>
#define fi first 
#define se second
#define int long long 
const int N =2e5+5 ,  oo = 1e9 ;
const ll sm = 1e9+7,cs=330 ,inf = 1e17; 
struct edge 
{
    int u , v , w;  
    bool operator <(const edge& a  )const 
    {
        return w<a.w; 
    }
};
int n ; 
vector<int>a;
vector<edge>q;
int pa[N];
int max_val;  
void inp()
{
    cin>> n; 
    a.resize(n) ; 
    for(int i= 0;i<n;i++)
    {
        cin>>a[i] ; 
    }
    sort(a.begin(),a.end()); 
    a.resize(unique(a.begin(),a.end())-a.begin());
    n = a.size() ;      
    max_val=a.back() ;
}

void init()
{
    for(int i =0 ;i<n;i++)
    {
        pa[i] =  i ;
    }
}
void build()
{
    for(int i=0;i<n-1;i++)
    {
        for(int j =a[i];j<=max_val;j+=a[i])
        {
            int pos = lower_bound(a.begin()+i+1,a.end(),j) - a.begin() ; 
            if(pos>=n)continue ; 
            if(a[pos]-j>a[i])continue ;
            q.pb({i,pos,a[pos]-j}) ;  
        }
    }
}
ll res=0 ;  
ll goc(int u )
{
    return (pa[u]==u?u:pa[u]=goc(pa[u])) ;
}   
void hop(int u , int v ,int w )
{
    int chau=goc(u) ; 
    int chav=goc(v) ; 
    if(chau==chav)return ;
    res+=w;  
    pa[chau]=chav; 
}
void solve()
{
    sort(q.begin(),q.end()) ; 
    for(int i= 0 ;i<q.size();i++)
    {
        int  u =q[i].u ; 
        int v =q[i].v ;  
        hop(u,v,q[i].w) ;       
    }
    cout<<res ; 
}
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0) ; cout.tie(0);
    int t ; 
    t = 1; 
    while(t--)
    {
        inp(); 
        init(); 
        build(); 
        solve() ; 
    }
    return 0;
}

Compilation message

sirni.cpp: In function 'void solve()':
sirni.cpp:75:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i= 0 ;i<q.size();i++)
      |                   ~^~~~~~~~~
sirni.cpp: At global scope:
sirni.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 54 ms 6600 KB Output is correct
3 Correct 3 ms 788 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 517 ms 2124 KB Output is correct
3 Correct 3 ms 788 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 660 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 27208 KB Output is correct
2 Correct 660 ms 100932 KB Output is correct
3 Correct 267 ms 51716 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6844 KB Output is correct
2 Correct 342 ms 100296 KB Output is correct
3 Correct 186 ms 26996 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 101108 KB Output is correct
2 Correct 879 ms 199576 KB Output is correct
3 Correct 267 ms 51928 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 13504 KB Output is correct
2 Correct 841 ms 199388 KB Output is correct
3 Correct 244 ms 51716 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 52100 KB Output is correct
2 Runtime error 2146 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 51876 KB Output is correct
2 Runtime error 2091 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 6980 KB Output is correct
2 Runtime error 1953 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -