oj.uz

Submission #827108

# Submission time Handle Problem Language Result Execution time Memory
827108 2023-08-16T08:48:32 Z vnm06 Simurgh (IOI17_simurgh) C++14
51 / 100
 1022 ms 1972 KB 
#include<bits/stdc++.h>
#include "simurgh.h"

using namespace std;

int sg=0;
int par[500], db[500];
bool prov[500000];
int ans[500000];
vector<int> added_edges;

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
    int m=u.size();
    for(int i=0; i<n; i++)
    {
        ///for(int j=0; j<sg; j++) //cout<<added_edges[j]<<" ";
        //cout<<endl;
        if(added_edges.size()==n-1) return added_edges;
        for(int i=0; i<n; i++)
        {
            par[i]=i;
            db[i]=1;
        }
        for(int j=0; j<sg; j++)
        {
            int v1=u[added_edges[j]], v2=v[added_edges[j]];
            while(v1!=par[v1]) v1=par[v1];
            while(v2!=par[v2]) v2=par[v2];
            if(db[v1]>db[v2]) par[v2]=v1;
            else if(db[v1]>db[v2]) par[v1]=v2;
            else
            {
                par[v2]=v1;
                db[v1]++;
            }
        }
        ///for(int i=0; i<n; i++) //cout<<par[i]<<endl;
        int cmp;
        for(cmp=0;; cmp++)
        {
            if(cmp>n) return added_edges;
        if(par[cmp]!=cmp) continue;
        for(int j=0; j<m; j++)
        {
            int v1=u[j], v2=v[j];
            while(v1!=par[v1]) v1=par[v1];
            while(v2!=par[v2]) v2=par[v2];
            if(v1==v2 || v1==cmp || v2==cmp) continue;
            added_edges.push_back(j);
            if(db[v1]>db[v2]) par[v2]=v1;
            else if(db[v1]>db[v2]) par[v1]=v2;
            else
            {
                par[v2]=v1;
                db[v1]++;
            }
        }




        if(added_edges.size()==n-2) break;
        added_edges.resize(sg);

        for(int i=0; i<n; i++)
        {
            par[i]=i;
            db[i]=1;
        }
        for(int j=0; j<sg; j++)
        {
            int v1=u[added_edges[j]], v2=v[added_edges[j]];
            while(v1!=par[v1]) v1=par[v1];
            while(v2!=par[v2]) v2=par[v2];
            if(db[v1]>db[v2]) par[v2]=v1;
            else if(db[v1]>db[v2]) par[v1]=v2;
            else
            {
                par[v2]=v1;
                db[v1]++;
            }
        }
        }

        int mist=1e9, mast=-1;
        for(int j=0; j<m; j++) ans[j]=-1;
        for(int j=0; j<m; j++)
        {
            if(prov[j]) continue;
            int v1=u[j], v2=v[j];
            while(v1!=par[v1]) v1=par[v1];
            while(v2!=par[v2]) v2=par[v2];
            if(v1!=cmp && v2!=cmp) continue;
            if(v1==v2) continue;
            prov[j]=1;
            added_edges.push_back(j);
            ans[j]=count_common_roads(added_edges);
            if(ans[j]>mast) mast=ans[j];
            if(ans[j]<mist) mist=ans[j];
            added_edges.resize(added_edges.size()-1);
        }
        added_edges.resize(sg);
        for(int j=0; j<m; j++)
        {
            if(ans[j]==mast)
            {
                added_edges.push_back(j);
                sg++;
            }
        }
    }
	return added_edges;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:19:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         if(added_edges.size()==n-1) return added_edges;
      |            ~~~~~~~~~~~~~~~~~~^~~~~
simurgh.cpp:63:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         if(added_edges.size()==n-2) break;
      |            ~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 312 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 ms 312 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 212 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 1 ms 316 KB correct
21 Correct 2 ms 352 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 312 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 308 KB correct
27 Correct 2 ms 304 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 316 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 308 KB correct
33 Correct 2 ms 212 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 312 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 ms 312 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 212 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 1 ms 316 KB correct
21 Correct 2 ms 352 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 312 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 308 KB correct
27 Correct 2 ms 304 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 316 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 308 KB correct
33 Correct 2 ms 212 KB correct
34 Correct 561 ms 1108 KB correct
35 Correct 450 ms 1080 KB correct
36 Correct 386 ms 852 KB correct
37 Correct 32 ms 340 KB correct
38 Correct 688 ms 1104 KB correct
39 Correct 271 ms 980 KB correct
40 Correct 155 ms 828 KB correct
41 Correct 27 ms 1092 KB correct
42 Correct 25 ms 1032 KB correct
43 Correct 251 ms 720 KB correct
44 Correct 266 ms 648 KB correct
45 Correct 233 ms 652 KB correct
46 Correct 249 ms 608 KB correct
47 Correct 148 ms 432 KB correct
48 Correct 31 ms 340 KB correct
49 Correct 29 ms 340 KB correct
50 Correct 71 ms 340 KB correct
51 Correct 280 ms 704 KB correct
52 Correct 178 ms 648 KB correct
53 Correct 157 ms 600 KB correct
54 Correct 249 ms 728 KB correct
55 Correct 219 ms 700 KB correct
56 Correct 181 ms 724 KB correct
57 Correct 184 ms 724 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB correct
2 Correct 1 ms 212 KB correct
3 Incorrect 1022 ms 1972 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB correct
2 Correct 0 ms 212 KB correct
3 Correct 0 ms 212 KB correct
4 Correct 0 ms 212 KB correct
5 Correct 0 ms 212 KB correct
6 Correct 0 ms 212 KB correct
7 Correct 0 ms 212 KB correct
8 Correct 0 ms 212 KB correct
9 Correct 0 ms 212 KB correct
10 Correct 0 ms 212 KB correct
11 Correct 0 ms 212 KB correct
12 Correct 0 ms 212 KB correct
13 Correct 0 ms 212 KB correct
14 Correct 3 ms 312 KB correct
15 Correct 1 ms 340 KB correct
16 Correct 1 ms 312 KB correct
17 Correct 3 ms 340 KB correct
18 Correct 1 ms 212 KB correct
19 Correct 3 ms 340 KB correct
20 Correct 1 ms 316 KB correct
21 Correct 2 ms 352 KB correct
22 Correct 2 ms 340 KB correct
23 Correct 2 ms 212 KB correct
24 Correct 2 ms 312 KB correct
25 Correct 1 ms 212 KB correct
26 Correct 2 ms 308 KB correct
27 Correct 2 ms 304 KB correct
28 Correct 1 ms 212 KB correct
29 Correct 1 ms 316 KB correct
30 Correct 2 ms 340 KB correct
31 Correct 2 ms 212 KB correct
32 Correct 2 ms 308 KB correct
33 Correct 2 ms 212 KB correct
34 Correct 561 ms 1108 KB correct
35 Correct 450 ms 1080 KB correct
36 Correct 386 ms 852 KB correct
37 Correct 32 ms 340 KB correct
38 Correct 688 ms 1104 KB correct
39 Correct 271 ms 980 KB correct
40 Correct 155 ms 828 KB correct
41 Correct 27 ms 1092 KB correct
42 Correct 25 ms 1032 KB correct
43 Correct 251 ms 720 KB correct
44 Correct 266 ms 648 KB correct
45 Correct 233 ms 652 KB correct
46 Correct 249 ms 608 KB correct
47 Correct 148 ms 432 KB correct
48 Correct 31 ms 340 KB correct
49 Correct 29 ms 340 KB correct
50 Correct 71 ms 340 KB correct
51 Correct 280 ms 704 KB correct
52 Correct 178 ms 648 KB correct
53 Correct 157 ms 600 KB correct
54 Correct 249 ms 728 KB correct
55 Correct 219 ms 700 KB correct
56 Correct 181 ms 724 KB correct
57 Correct 184 ms 724 KB correct
58 Correct 1 ms 212 KB correct
59 Correct 1 ms 212 KB correct
60 Incorrect 1022 ms 1972 KB WA in grader: NO
61 Halted 0 ms 0 KB -