Submission #297860

#	Time	Username	Problem	Language	Result	Execution time	Memory
297860		Autoratch	Simurgh (IOI17_simurgh)	C++14	30 / 100	157 ms	4800 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];
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();
            for(int x : cmp[j])
            {
                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;
}

Compilation message (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: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30