Submission #858837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858837	2023-10-09T08:57:05 Z	danikoynov	Newspapers (CEOI21_newspapers)	C++14	77 / 100	12 ms	600 KB

newspapers

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1010;
int n, m;
vector < int > adj[maxn];

int used[maxn], rev[maxn];
void bfs(int v)
{
    for (int i = 1; i <= n; i ++)
        used[i] = -1;
    used[v] = 0;
    rev[v] = 0;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (int u : adj[cur])
        {
            if (used[u] == -1)
            {
                used[u] = used[cur] + 1;
                rev[u] = cur;
                q.push(u);
            }
        }
    }
}

vector < pair < int, int > > acc[maxn];

    vector < int > seq;
vector < int > act;

int mark[maxn];
void add_to_seq(int ver)
{
    seq.push_back(ver);
    int i = 0;
    while(i < act.size() && act[i] != ver)
        i ++;
    if (i != act.size())
        act.erase(act.begin() + i);

    for (int i = 1; i <= n; i ++)
    {
        mark[i] = 0;
    }
    vector < int > new_act;
    for (int v : act)
    {
        for (int u : adj[v])
            mark[u] = 1;
    }


    for (int i = 1; i <= n; i ++)
        if (mark[i])
        new_act.push_back(i);

    act = new_act;
}


int get_dfs(int v, int p)
{
    if (mark[v])
        return v;
    for (int u : adj[v])
    {
        if (u == p || used[u])
            continue;
        int tr = get_dfs(u, v);
        if (tr != -1)
            return tr;
    }

        for (int u : adj[v])
    {
        if (u == p || !used[u])
            continue;
        int tr = get_dfs(u, v);
        if (tr != -1)
            return tr;
    }
    return -1;
}
void solve()
{
    cin >> n >> m;
    if (m != n - 1)
    {
        cout << "NO" << endl;
        return;
    }
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    if (n == 1)
    {
        cout << "YES" << endl << 1 << endl << 1 << endl;
        return;
    }

    if (n == 2)
    {
        cout << "YES" << endl << 2 << endl << "1 1" << endl;
        return;
    }

    bfs(1);
    int s = 1;
    for (int i = 1; i <= n; i ++)
        if (used[i] > used[s])
        s = i;

    bfs(s);
    int t = 1;
    for (int i = 1; i <= n; i ++)
        if (used[i] > used[t])
            t = i;
        /**for (int i = 1; i <= n; i ++)
            cout << used[i] << " ";
        cout << endl;*/

    vector < int > chain;
    int ver = t;
    while(ver != s)
    {
        chain.push_back(ver);
        ver = rev[ver];
    }
    chain.push_back(ver);
    reverse(chain.begin(), chain.end());

    /**cout << "-----------" << endl;
    for (int cur : chain)
        cout << cur << " ";
    cout << endl;*/
    for (int i = 1; i <= n; i ++)
    {
        used[i] = 0;
    }

    chain.erase(chain.begin());
    chain.pop_back();

    for (int cur : chain)
    {
        used[cur] = 1;
    }

    for (int cur : chain)
    {
        for (int nb : adj[cur])
        {
            if (used[nb])
                continue;
            for (int u : adj[nb])
            {
                if (u != cur)
                {
                    for (int d : adj[u])
                    {
                        if (d != nb)
                        {
                            cout << "NO" << endl;
                            return;
                        }
                    }
                    acc[cur].push_back({nb, u});
                }
            }
        }
    }

    /**for (int cur : chain)
        cout << cur << " ";
    cout << endl;*/
    for (int i = 1; i <= n; i ++)
    act.push_back(i);

    for (int cur : chain)
    {
        add_to_seq(cur);
        for (pair < int, int > d : acc[cur])
        {
                   add_to_seq(d.first);
                   add_to_seq(cur);
        }
    }

    reverse(chain.begin(), chain.end());


    for (int cur : chain)
    {
        add_to_seq(cur);
        for (pair < int, int > d : acc[cur])
        {
                   add_to_seq(d.first);
                   add_to_seq(cur);
        }
    }
    ///exit(0);
    /**int cnt = 0;
    while(act.size() > 0)
    {

        for (int i = 1; i <= n; i ++)
            mark[i] = 0;
        for (int cur : act)
            mark[cur] = 1;

        cnt ++;
        assert(cnt < 10 * n);
        int ver = get_dfs(s, -1);
        ///cout << "action " << ver << endl;
        add_to_seq(ver);
    }*/

    cout << "YES" << endl;
    cout << seq.size() << endl;
    for (int cur : seq)
        cout << cur << " ";
    cout << endl;



}

int main()
{
    solve();
    return 0;
}
/**
9 8
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9


*/

Compilation message

newspapers.cpp: In function 'void add_to_seq(int)':
newspapers.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(i < act.size() && act[i] != ver)
      |           ~~^~~~~~~~~~~~
newspapers.cpp:63:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (i != act.size())
      |         ~~^~~~~~~~~~~~~

Subtask #1
9.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	344 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	1 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	1 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	0 ms	348 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Partially correct	0 ms	348 KB	Provide a successful but not optimal strategy.
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	1 ms	348 KB	Output is correct
53	Correct	0 ms	348 KB	Output is correct
54	Partially correct	0 ms	348 KB	Provide a successful but not optimal strategy.
55	Correct	0 ms	348 KB	Output is correct
56	Correct	0 ms	348 KB	Output is correct
57	Correct	0 ms	348 KB	Output is correct
58	Correct	0 ms	348 KB	Output is correct
59	Correct	0 ms	348 KB	Output is correct
60	Correct	0 ms	348 KB	Output is correct
61	Correct	0 ms	348 KB	Output is correct
62	Correct	0 ms	348 KB	Output is correct
63	Correct	0 ms	348 KB	Output is correct
64	Correct	0 ms	344 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	8 ms	348 KB	Output is correct
12	Correct	3 ms	344 KB	Output is correct
13	Correct	4 ms	348 KB	Output is correct
14	Correct	4 ms	348 KB	Output is correct
15	Correct	4 ms	348 KB	Output is correct
16	Correct	10 ms	500 KB	Output is correct
17	Correct	9 ms	348 KB	Output is correct
18	Correct	9 ms	344 KB	Output is correct
19	Correct	9 ms	344 KB	Output is correct
20	Correct	10 ms	348 KB	Output is correct

Subtask #3
60.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	344 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	1 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	1 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	0 ms	348 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	0 ms	348 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	0 ms	348 KB	Output is correct
48	Partially correct	0 ms	348 KB	Provide a successful but not optimal strategy.
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	1 ms	348 KB	Output is correct
53	Correct	0 ms	348 KB	Output is correct
54	Partially correct	0 ms	348 KB	Provide a successful but not optimal strategy.
55	Correct	0 ms	348 KB	Output is correct
56	Correct	0 ms	348 KB	Output is correct
57	Correct	0 ms	348 KB	Output is correct
58	Correct	0 ms	348 KB	Output is correct
59	Correct	0 ms	348 KB	Output is correct
60	Correct	0 ms	348 KB	Output is correct
61	Correct	0 ms	348 KB	Output is correct
62	Correct	0 ms	348 KB	Output is correct
63	Correct	0 ms	348 KB	Output is correct
64	Correct	0 ms	344 KB	Output is correct
65	Correct	1 ms	344 KB	Output is correct
66	Correct	0 ms	348 KB	Output is correct
67	Correct	0 ms	348 KB	Output is correct
68	Correct	0 ms	344 KB	Output is correct
69	Correct	0 ms	348 KB	Output is correct
70	Correct	1 ms	348 KB	Output is correct
71	Correct	0 ms	348 KB	Output is correct
72	Correct	1 ms	348 KB	Output is correct
73	Correct	0 ms	348 KB	Output is correct
74	Correct	0 ms	348 KB	Output is correct
75	Correct	0 ms	412 KB	Output is correct
76	Correct	0 ms	344 KB	Output is correct
77	Correct	0 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Correct	1 ms	348 KB	Output is correct
80	Correct	1 ms	348 KB	Output is correct
81	Correct	1 ms	348 KB	Output is correct
82	Correct	1 ms	348 KB	Output is correct
83	Correct	1 ms	348 KB	Output is correct
84	Correct	1 ms	348 KB	Output is correct
85	Correct	1 ms	348 KB	Output is correct
86	Correct	1 ms	344 KB	Output is correct
87	Correct	1 ms	348 KB	Output is correct
88	Correct	1 ms	344 KB	Output is correct
89	Partially correct	11 ms	348 KB	Provide a successful but not optimal strategy.
90	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
91	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
92	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
93	Partially correct	10 ms	344 KB	Provide a successful but not optimal strategy.
94	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
95	Partially correct	11 ms	348 KB	Provide a successful but not optimal strategy.
96	Partially correct	11 ms	548 KB	Provide a successful but not optimal strategy.
97	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
98	Partially correct	12 ms	348 KB	Provide a successful but not optimal strategy.
99	Partially correct	8 ms	344 KB	Provide a successful but not optimal strategy.
100	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
101	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
102	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
103	Partially correct	9 ms	348 KB	Provide a successful but not optimal strategy.
104	Partially correct	6 ms	348 KB	Provide a successful but not optimal strategy.
105	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
106	Partially correct	9 ms	348 KB	Provide a successful but not optimal strategy.
107	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
108	Partially correct	11 ms	548 KB	Provide a successful but not optimal strategy.
109	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
110	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
111	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
112	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
113	Partially correct	10 ms	348 KB	Provide a successful but not optimal strategy.
114	Partially correct	9 ms	348 KB	Provide a successful but not optimal strategy.
115	Partially correct	8 ms	348 KB	Provide a successful but not optimal strategy.
116	Partially correct	9 ms	348 KB	Provide a successful but not optimal strategy.
117	Partially correct	11 ms	544 KB	Provide a successful but not optimal strategy.
118	Partially correct	9 ms	348 KB	Provide a successful but not optimal strategy.
119	Partially correct	8 ms	548 KB	Provide a successful but not optimal strategy.
120	Partially correct	10 ms	348 KB	Provide a successful but not optimal strategy.
121	Partially correct	11 ms	344 KB	Provide a successful but not optimal strategy.
122	Partially correct	8 ms	344 KB	Provide a successful but not optimal strategy.
123	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
124	Partially correct	10 ms	348 KB	Provide a successful but not optimal strategy.
125	Partially correct	6 ms	348 KB	Provide a successful but not optimal strategy.
126	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
127	Partially correct	7 ms	348 KB	Provide a successful but not optimal strategy.
128	Partially correct	11 ms	544 KB	Provide a successful but not optimal strategy.
129	Correct	1 ms	344 KB	Output is correct
130	Correct	1 ms	600 KB	Output is correct
131	Correct	1 ms	348 KB	Output is correct
132	Correct	1 ms	348 KB	Output is correct
133	Correct	1 ms	348 KB	Output is correct
134	Correct	0 ms	348 KB	Output is correct
135	Correct	0 ms	344 KB	Output is correct
136	Correct	0 ms	348 KB	Output is correct
137	Correct	0 ms	348 KB	Output is correct
138	Correct	0 ms	348 KB	Output is correct
139	Correct	0 ms	344 KB	Output is correct
140	Correct	0 ms	544 KB	Output is correct
141	Correct	0 ms	348 KB	Output is correct
142	Correct	0 ms	348 KB	Output is correct
143	Correct	0 ms	348 KB	Output is correct
144	Correct	10 ms	348 KB	Output is correct
145	Correct	9 ms	540 KB	Output is correct

Submission #858837

Compilation message

Subtask #1 9.0 / 12.0

Subtask #2 8.0 / 8.0

Subtask #3 60.0 / 80.0

Subtask #1
9.0 / 12.0

Subtask #2
8.0 / 8.0

Subtask #3
60.0 / 80.0