답안 #766842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766842	2023-06-26T08:08:21 Z	danikoynov	Simurgh (IOI17_simurgh)	C++14	30 / 100	71 ms	3476 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 250;
struct disjoint_set_union
{
    int par[maxn];

    disjoint_set_union(){};

    disjoint_set_union(int n)
    {
        for (int i = 0; i < n; i ++)
            par[i] = i;
    }

    int find_leader(int v)
    {
        if (v == par[v])
            return v;
        return (par[v] = find_leader(par[v]));
    }

    bool is_connected(int v, int u)
    {
        return find_leader(v) == find_leader(u);
    }

    void unite(int v, int u)
    {
        v = find_leader(v);
        u = find_leader(u);
        if (v == u)
            return;
        par[v] = u;
    }
};
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	vector < int > gold;
	int m = u.size();
	for (int t = 0; t < n - 1; t ++)
    {
        disjoint_set_union dsu(n);
        int cp = n;
        vector < int > res;
        for (int edge : gold)
        {
            dsu.unite(u[edge], v[edge]);
             cp --;
             res.push_back(edge);
        }
        for (int j = 0; j < m && cp > 2; j ++)
        {
            if (!dsu.is_connected(u[j], v[j]))
            {
                dsu.unite(u[j], v[j]);
                cp --;
                res.push_back(j);
            }
        }
        vector < pair < int, int > > pot;
        for (int i = 0; i < m; i ++)
        {
            if (!dsu.is_connected(u[i], v[i]))
                pot.push_back({i, 0});
        }

        int mx = -1, rd = -1;
        for (int i = 0; i < pot.size(); i ++)
        {
            res.push_back(pot[i].first);
            pot[i].second = count_common_roads(res);
            if (pot[i].second > mx)
            {
                mx = pot[i].second;
                rd = pot[i].first;
            }
            res.pop_back();
        }

        gold.push_back(rd);
    }
	return gold;
}

Compilation message

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < pot.size(); i ++)
      |                         ~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	300 KB	correct
5	Correct	1 ms	300 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	272 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	300 KB	correct
5	Correct	1 ms	300 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	272 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	5 ms	308 KB	correct
15	Correct	4 ms	340 KB	correct
16	Correct	3 ms	300 KB	correct
17	Correct	5 ms	212 KB	correct
18	Correct	2 ms	304 KB	correct
19	Correct	4 ms	320 KB	correct
20	Correct	3 ms	212 KB	correct
21	Correct	4 ms	332 KB	correct
22	Correct	2 ms	308 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	2 ms	212 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	2 ms	212 KB	correct
27	Correct	2 ms	212 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	212 KB	correct
31	Correct	3 ms	212 KB	correct
32	Correct	3 ms	212 KB	correct
33	Correct	3 ms	300 KB	correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	300 KB	correct
5	Correct	1 ms	300 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	272 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	5 ms	308 KB	correct
15	Correct	4 ms	340 KB	correct
16	Correct	3 ms	300 KB	correct
17	Correct	5 ms	212 KB	correct
18	Correct	2 ms	304 KB	correct
19	Correct	4 ms	320 KB	correct
20	Correct	3 ms	212 KB	correct
21	Correct	4 ms	332 KB	correct
22	Correct	2 ms	308 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	2 ms	212 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	2 ms	212 KB	correct
27	Correct	2 ms	212 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	212 KB	correct
31	Correct	3 ms	212 KB	correct
32	Correct	3 ms	212 KB	correct
33	Correct	3 ms	300 KB	correct
34	Incorrect	71 ms	988 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	300 KB	correct
2	Correct	1 ms	212 KB	correct
3	Runtime error	12 ms	3476 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	1 ms	300 KB	correct
5	Correct	1 ms	300 KB	correct
6	Correct	1 ms	212 KB	correct
7	Correct	1 ms	212 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	1 ms	272 KB	correct
10	Correct	1 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	5 ms	308 KB	correct
15	Correct	4 ms	340 KB	correct
16	Correct	3 ms	300 KB	correct
17	Correct	5 ms	212 KB	correct
18	Correct	2 ms	304 KB	correct
19	Correct	4 ms	320 KB	correct
20	Correct	3 ms	212 KB	correct
21	Correct	4 ms	332 KB	correct
22	Correct	2 ms	308 KB	correct
23	Correct	2 ms	296 KB	correct
24	Correct	2 ms	212 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	2 ms	212 KB	correct
27	Correct	2 ms	212 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	212 KB	correct
31	Correct	3 ms	212 KB	correct
32	Correct	3 ms	212 KB	correct
33	Correct	3 ms	300 KB	correct
34	Incorrect	71 ms	988 KB	WA in grader: NO
35	Halted	0 ms	0 KB	-

답안 #766842

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0