제출 #297873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297873		Autoratch	Simurgh (IOI17_simurgh)	C++14	51 / 100	176 ms	4472 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 501;

int n,m;
vector<pair<int,int> > adj[N];
vector<int> r,ans,tmp,ask,tmp2;
bool visited[N],computed[N*N];
vector<vector<int> > cmp;
int ed[N][N];
set<int> ts;

void dfs(int u,int f)
{
    if(visited[u]) return;
    visited[u] = true;
    tmp.push_back(u);
    for(auto [id,v] : adj[u]) if(!visited[v] and v!=f) r.push_back(id),dfs(v,f);
}

std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) 
{
    n = _n,m = u.size();
    for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) ed[i][j] = -1;
    for(int i = 0;i < m;i++)
    {
        int a = u[i],b = v[i];
        adj[a].push_back({i,b});
        adj[b].push_back({i,a});
        ed[a][b] = ed[b][a] = i;
    }
    for(int i = 0;i < n;i++)
    {
        r.clear();
        tmp.clear();
        cmp.clear();
        for(int j = 0;j < n;j++) visited[j] = false;
        for(int j = 0;j < n;j++) if(!visited[j] and j!=i) dfs(j,i),cmp.push_back(tmp),tmp.clear();
        int cm = cmp.size();
        for(int j = 0;j < cm;j++) 
        {
            tmp.clear();
            for(int x : cmp[j]) if(ed[i][x]!=-1) tmp.push_back(ed[i][x]);
            swap(cmp[j],tmp);
        }
        for(int j = 0;j < cm;j++) 
        {
            tmp.clear();
            tmp = r;
            for(int k = 0;k < cm;k++) if(k!=j) tmp.push_back(cmp[k][0]);
            int mx = -1;
            tmp2.clear();
            bool used = false;
            for(int x : cmp[j]) 
            {
                if(computed[x])
                {
                    if(ts.find(x)!=ts.end() and !used) used = true;
                    else continue;
                }
                computed[x] = true;
                ask = tmp;
                ask.push_back(x);
                int ret = count_common_roads(ask);
                if(ret>mx) mx = ret,tmp2.clear(),tmp2.push_back(x);
                else if(ret==mx) tmp2.push_back(x);
            }
            for(int x : tmp2) ts.insert(x);
        }        
    }
    for(int x : ts) ans.push_back(x);
    return ans;
}

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

simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto [id,v] : adj[u]) if(!visited[v] and v!=f) r.push_back(id),dfs(v,f);
      |              ^

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