oj.uz

답안 #568433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568433 2022-05-25T11:59:45 Z shahriarkhan Sirni (COCI17_sirni) C++14
140 / 140
 4105 ms 773864 KB 
#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e7 + 5 ;

int nex[MX] ;

vector<pair<int,int> > val[MX] ;

struct dsu
{
    vector<int> sz , par ;
    void init(int n)
    {
        sz = vector<int> (n+2,0) ;
        par = vector<int> (n+2,0) ;
        for(int i = 1 ; i <= n ; ++i)
        {
            par[i] = i , sz[i] = 1 ;
        }
    }
    int find_root(int a)
    {
        if(par[a]==a) return a ;
        return par[a] = find_root(par[a]) ;
    }
    int union_edge(int u , int v)
    {
        int root_u = find_root(u) , root_v = find_root(v) ;
        if(root_u==root_v) return 0 ;
        if(sz[root_v]>sz[root_u]) swap(root_u,root_v) ;
        sz[root_u] += sz[root_v] ;
        par[root_v] = root_u ;
        return 1 ;
    }
};

int main()
{
    int n ;
    scanf("%d",&n) ;
    vector<int> go ;
    int p[n+2] = {0} ;
    long long ans = 0 ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%d",&p[i]) ;
        if(!nex[p[i]]) nex[p[i]] = i , go.push_back(i) ;
    }
    for(int i = MX - 2 ; i >= 0 ; --i)
    {
        if(!nex[i]) nex[i] = nex[i+1] ;
    }
    dsu D ;
    D.init(n+2) ;
    for(int i : go)
    {
        for(int j = p[i] ; j < MX ; j += p[i])
        {
            if(!nex[j+(j==p[i])]) continue ;
            int rem = p[nex[j+(j==p[i])]]%p[i] ;
            val[rem].push_back({i,nex[j+(j==p[i])]}) ;
        }
    }
    for(int i = 0 ; i < MX ; ++i)
    {
        for(pair<int,int> &f : val[i])
        {
            int st = D.union_edge(f.first,f.second) ;
            if(st) ans += i ;
        }
    }
    printf("%lld\n",ans) ;
    return 0 ;
}

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
sirni.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d",&p[i]) ;
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 274408 KB Output is correct
2 Correct 329 ms 306740 KB Output is correct
3 Correct 207 ms 274568 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 274364 KB Output is correct
2 Correct 1845 ms 700836 KB Output is correct
3 Correct 227 ms 275108 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 227 ms 274416 KB Output is correct
2 Correct 226 ms 274324 KB Output is correct
3 Correct 226 ms 274380 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 285624 KB Output is correct
2 Correct 856 ms 313200 KB Output is correct
3 Correct 488 ms 299060 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 276476 KB Output is correct
2 Correct 722 ms 299200 KB Output is correct
3 Correct 571 ms 285948 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 716 ms 297632 KB Output is correct
2 Correct 1137 ms 331828 KB Output is correct
3 Correct 461 ms 294828 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 393 ms 278480 KB Output is correct
2 Correct 1202 ms 334004 KB Output is correct
3 Correct 518 ms 296196 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 289792 KB Output is correct
2 Correct 2213 ms 659668 KB Output is correct
3 Correct 365 ms 293460 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 293984 KB Output is correct
2 Correct 3849 ms 773864 KB Output is correct
3 Correct 618 ms 354612 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 276976 KB Output is correct
2 Correct 4105 ms 660080 KB Output is correct
3 Correct 499 ms 298016 KB Output is correct