oj.uz

답안 #714291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714291 2023-03-24T08:02:16 Z vjudge1 Art Collections (BOI22_art) C++17
0 / 100
 1 ms 208 KB 
#include <bits/stdc++.h>
#include "art.h"

using namespace std;

typedef long long ll;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define endl "\n"
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) \
                    cout << v[i] << " "; \
                    cout<<endl;
struct DSU {
	vector<int> e;

	void init(int n)
	{
	    e.assign(n, -1);
	}

	int get(int x)
	{
	    if (e[x] < 0)
            return x;
        return get(e[x]);
	}

	bool together(int a, int b)
	{
	    if (get(a) == get(b))
            return true;
        return false;
	}

	int s(int x)
	{
	    return -e[get(x)];
	}

	bool un(int x, int y)
	{
		x = get(x);
        y = get(y);

		if (x == y) return false;

		if (e[x] > e[y]) swap(x, y);

		e[x] += e[y];
		e[y] = x;

		return true;
	}
};
vector<int> adj[41];
vector<int> s(41, 0);
vector<int> ans;
vector<int> indeg(41, 0);

int dfs1(int a)
{
    s[a] = 1;
    
    int temp = 0;

    for (int i = 0; i < adj[a].size(); i++)
    {
        if (s[adj[a][i]]) temp = max(temp, s[adj[a][i]]);
        else temp = max(temp, dfs1(adj[a][i]));
    }
    s[a] += temp;

    return s[a];
}

void dfs(int a)
{
    ans.pb(a);
    for (int i = 0; i < adj[a].size(); i++)
    {
        if (s[adj[a][i]] == s[a] - 1)
        {
            dfs(adj[a][i]);
        }
    }
}

void solve(int n)
{
    vector<int> v;
    for (int i = 1; i <= n; i++)
    {
        v.pb(i);
    }

    for (int i = 1; i <= n; i++)
    {
        swap(v[0], v[i - 1]);
        int x = publish(v);
        for (int j = i + 1; j <= n; j++)
        {
            swap(v[0], v[j - 1]);
            int y = publish(v);
            swap(v[0], v[j - 1]);

            if (y < x)
            {
                adj[x].pb(y);
                indeg[y]++;
            }
            else
            {
                adj[y].pb(x);
                indeg[x]++;
            }
        }
        swap(v[0], v[i - 1]);
    }
    int root;
    for (int i = 1; i <= n; i++)
    {
        if (!indeg[i])
        {
            root = i;
        }
    }
    dfs1(root);
    dfs(root);
    answer(ans);
}

Compilation message

art.cpp: In function 'int dfs1(int)':
art.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
art.cpp: In function 'void dfs(int)':
art.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
art.cpp: In function 'void solve(int)':
art.cpp:141:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     dfs(root);
      |     ~~~^~~~~~
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 208 KB Not correct
2 Halted 0 ms 0 KB -