oj.uz

Submission #234892

# Submission time Handle Problem Language Result Execution time Memory
234892 2020-05-26T07:13:40 Z mahmoudbadawy Sirni (COCI17_sirni) C++17
140 / 140
 3817 ms 711516 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int N=1e5+5,M=1e7+7;
     
    int n;
    int arr[N];
    vector< pair<int,int> > ed[M];
    int uni[N];
     
    int uni_find(int x)
    {
    	return uni[x]=(uni[x]==x?x:uni_find(uni[x]));
    }
     
    int unio(int x,int y)
    {
    	x=uni_find(x); y=uni_find(y);
    	if(x==y) return 0;
    	uni[x]=y;
    	return 1;
    }
     
    int main()
    {
    	scanf("%d",&n);
    	set<int> ss;
    	for(int i=0;i<n;i++)
    	{
    		scanf("%d",&arr[i]);
    		ss.insert(arr[i]);
    	}
    	n=0;
    	for(int i:ss) arr[n++]=i;
    	for(int i=0;i<n;i++)
    	{
    		int s=i+1;
    		for(int j=arr[i];j<M;j+=arr[i])
    		{
    			while(s<n && arr[s]<j) s++;
    			if(s<n) ed[arr[s]%arr[i]].emplace_back(i,s);
    		}
    	}
    	iota(uni,uni+n,0);
    	long long ans=0;
    	for(int i=0;i<M;i++)
    	{
    		for(auto j:ed[i])
    		{
    			if(unio(j.first,j.second)) ans+=i;
    		}
    	}
    	cout << ans << endl;
    }

Compilation message

sirni.cpp: In function 'int main()':
sirni.cpp:27:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d",&n);
      ~~~~~^~~~~~~~~
sirni.cpp:31:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&arr[i]);
       ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 235384 KB Output is correct
2 Correct 241 ms 264440 KB Output is correct
3 Correct 157 ms 235640 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 235384 KB Output is correct
2 Correct 1447 ms 630460 KB Output is correct
3 Correct 160 ms 236024 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 235384 KB Output is correct
2 Correct 163 ms 235308 KB Output is correct
3 Correct 156 ms 235388 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2385 ms 250248 KB Output is correct
2 Correct 2222 ms 278352 KB Output is correct
3 Correct 1682 ms 260048 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 237816 KB Output is correct
2 Correct 307 ms 259192 KB Output is correct
3 Correct 1729 ms 249672 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2461 ms 262088 KB Output is correct
2 Correct 2456 ms 297288 KB Output is correct
3 Correct 2322 ms 259588 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 240456 KB Output is correct
2 Correct 1761 ms 296044 KB Output is correct
3 Correct 1889 ms 260436 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1766 ms 253484 KB Output is correct
2 Correct 3125 ms 599412 KB Output is correct
3 Correct 1773 ms 256176 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1778 ms 257956 KB Output is correct
2 Correct 3817 ms 711516 KB Output is correct
3 Correct 1862 ms 313104 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 238448 KB Output is correct
2 Correct 3318 ms 598540 KB Output is correct
3 Correct 1997 ms 263100 KB Output is correct