oj.uz

Submission #973452

# Submission time Handle Problem Language Result Execution time Memory
973452 2024-05-02T02:39:10 Z modwwe Sjekira (COCI20_sjekira) C++17
110 / 110
 41 ms 15340 KB 
#include<bits/stdc++.h>
#define int long long
#define d0 1
#define d1 11
#define d2 101
#define d3 1001
#define d4 10001
#define d5 400001
#define d6 1000001
#define down cout<<'\n';
#define NMT     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define debug(x) cerr<<x<<" ";
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "a"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define sz(s) s.size()
#define pii pair<int,int>
#define checktime   cout << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void bieoiibe();
void de();
template<typename A, typename B>istream& operator>>(istream& in, pair<A, B> &v){in >> v.first >> v.second;return in;}
template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v){out << v.first << " " << v.second << " ";return out;}
template < class T > bool minimize(T& a, const T& b){    return b < a ? a = b, 1 : 0;}
template < class T > bool maximize(T& a, const T& b){return a < b ? a = b, 1 : 0;}
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count    ());
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dx2[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy2[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int mod2=1e9+7;
const int mod=1073741824;
const int  mod1=998244353;
//struct trie{int ck[2],cnt;}t[10000005];
string x;
struct ib{int a,b;};
struct ic{int a,b,c;};
struct id{int a,b,c,d;};
int minn=1e18,maxx=-1e9;
int n,m,s2,s4,s3,sf,k,s5,l,r,dem=0,res=0,mx;
int  s;
int el=29;
ic ds[d5*2];
int a[2*d5];
vector<ic> v;
main()
{
#ifndef ONLINE_JUDG E
    //fin(task),fou(task);
#endif
NMT
  // modwwe
    bieoiibe(),down

}
void reset(int x){
    ds[x]={x,1,a[x]};
}
int tim(int x)
{
    if(ds[x].a==x) return x;
    ds[x].a=tim(ds[x].a);
    return ds[x].a;
}
void noi(int x,int y)
{
     x=tim(x);y=tim(y);
      if(x!=y)
      {
          if(ds[x].b<ds[y].b) swap(x,y);
          ds[y].a=x;
          ds[x].c=max(ds[x].c,ds[y].c);
     ds[x].b+=ds[y].b;
      }
}
bool cmp(ic a,ic  b)
{
    return a.c<b.c;
}
void bieoiibe()///TR AN GNG
{
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i],reset(i);
    }
    for(int i=1;i<n;i++)
    {
        cin>>l>>r;
        v.push_back({l,r,max(a[l],a[r])});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++)
    {
        s2=tim(v[i].a);
        s3=tim(v[i].b);
        if(s2!=s3)
        {
            s+=ds[s2].c+ds[s3].c;
            noi(v[i].a,v[i].b);
        }
    }
    cout<<s;

}

Compilation message

sjekira.cpp:51:21: warning: extra tokens at end of #ifndef directive
   51 | #ifndef ONLINE_JUDG E
      |                     ^
sjekira.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main()
      | ^~~~
sjekira.cpp: In function 'void bieoiibe()':
sjekira.cpp:96:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<ic>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11728 KB Output is correct
2 Correct 27 ms 9676 KB Output is correct
3 Correct 24 ms 9588 KB Output is correct
4 Correct 24 ms 11248 KB Output is correct
5 Correct 36 ms 13936 KB Output is correct
6 Correct 38 ms 15340 KB Output is correct
7 Correct 33 ms 12236 KB Output is correct
8 Correct 29 ms 12752 KB Output is correct
9 Correct 22 ms 9424 KB Output is correct
10 Correct 35 ms 15044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2592 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 30 ms 11728 KB Output is correct
7 Correct 27 ms 9676 KB Output is correct
8 Correct 24 ms 9588 KB Output is correct
9 Correct 24 ms 11248 KB Output is correct
10 Correct 36 ms 13936 KB Output is correct
11 Correct 38 ms 15340 KB Output is correct
12 Correct 33 ms 12236 KB Output is correct
13 Correct 29 ms 12752 KB Output is correct
14 Correct 22 ms 9424 KB Output is correct
15 Correct 35 ms 15044 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2592 KB Output is correct
21 Correct 8 ms 8108 KB Output is correct
22 Correct 7 ms 5976 KB Output is correct
23 Correct 41 ms 13624 KB Output is correct
24 Correct 23 ms 11216 KB Output is correct
25 Correct 24 ms 12484 KB Output is correct
26 Correct 18 ms 9168 KB Output is correct
27 Correct 18 ms 9420 KB Output is correct
28 Correct 22 ms 10956 KB Output is correct
29 Correct 16 ms 9172 KB Output is correct
30 Correct 36 ms 14588 KB Output is correct