제출 #265324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
265324		arayi	Simurgh (IOI17_simurgh)	C++17	0 / 100	8 ms	12160 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
#define ask count_common_roads
using namespace std;

const int N = 500 * 500 + 500;

int col[N], ind[N];
vector <pair <int, int> > g[N];
vector <int> sm;
vector <int> a[N], fp;
bool cl[N];
void dfs(int v)
{
    a[v] = fp;
    cl[v] = true;
    for(auto p : g[v])
    {
        if(cl[p.fr]) continue;
        ind[p.sc] = sm.size();
        sm.ad(p.sc);
        fp.ad(p.sc);
        dfs(p.fr);
        fp.pop_back();
    }
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	for (int i = 0; i < u.size(); i++)
	{
	    g[u[i]].ad(MP(v[i], i));
	    g[v[i]].ad(MP(u[i], i));
	}
	dfs(0);
	//for(auto p : sm) cout << p << " ";
	//cout << endl;
	int ss = ask(sm);
	for (int i = 0; i < u.size(); i++)
	{
	    if(a[u[i]].size() <=  a[v[i]].size() + 1) swap(u[i], v[i]);
	    if(a[u[i]].size() <=  a[v[i]].size() + 1) continue;
	    //cout << i << endl;
	    vector <int> b;
	    for (int j = a[v[i]].size(); j < a[u[i]].size(); j++)
	        b.ad(a[u[i]][j]);
        bool bl = 0;
        for(auto p : b)
        {
            if(col[p] == -1)
            {
                sm[ind[p]] = i;
                if(ask(sm) == ss) col[i] = -1;
                else col[i] = 1;
                sm[ind[p]] = p;
                bl = true;
                break;
            }
            else
            {
                sm[ind[p]] = i;
                if(ask(sm) == ss) col[i] = 1;
                else col[i] = -1;
                sm[ind[p]] = p;
                bl = true;
                break;
            }
        }
        if(bl)
        {
            for(auto p : b)
            {
                if(col[p] == 0)
                {
                    sm[ind[p]] = i;
                    if(ask(sm) == ss) col[p] = col[i];
                    else col[p] = 0 - col[i];
                    sm[ind[p]] = p;
                }
            }
            continue;
        }
        vector <pair<int, int> > c;
        c.ad(MP(ss, i));
        for(auto p : b)
        {
            sm[ind[p]] = i;
            int i1 = ask(sm);
            c.ad(MP(p, i1));
            sm[ind[p]] = p;
        }
        for(auto p : c)
        {
            if(c[0].fr == p.fr) col[p.sc] = 1;
            else col[p.sc] = -1;
        }
	}
	vector <int> pat;
	for (int i = 0; i < u.size(); i++)
	{
	    if(col[i] >= 0) pat.ad(i);
	}
	return pat;
}
/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~
simurgh.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~
simurgh.cpp:47:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |      for (int j = a[v[i]].size(); j < a[u[i]].size(); j++)
      |                                   ~~^~~~~~~~~~~~~~~~
simurgh.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30