Submission #1326421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326421		eri16	Simurgh (IOI17_simurgh)	C++20	51 / 100	130 ms	5232 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"

using namespace std;

using ll = long long;

vector <int> adj[250];
vector <int> ans(60000,0);
vector <int> ans2(60000,0);

int vis[250];
map <pair<int,int>,int> mp;

int color=0;
vector <int> edges[250];

void dfs(int node, int parent){
    for (auto child : adj[node]){
        if (vis[child]==-1 && child!=parent){
            vis[child]=color;
            edges[color].push_back(mp[{node,child}]);
            dfs(child,node);
        }
    }
}
/*
int count_common_roads(vector<int> r){
    for (auto x : r){
        cout<<x<<' ';
    }
    int y;
    cin>>y;
    return y;
}
*/
vector<int> find_roads(int n, vector<int> angfang, vector<int> ende){
    
    int m = angfang.size();
    
    for (int i=0; i<m; i++){
        adj[angfang[i]].push_back(ende[i]);
        adj[ende[i]].push_back(angfang[i]);        
        
        mp[{angfang[i],ende[i]}]=i;
        mp[{ende[i],angfang[i]}]=i;
    }
    
    for (int node=0; node<n; node++){
        color=0;
        for (int i=0; i<n; i++){
            vis[i]=-1;
        }
        vis[node]=1000000;
        for (auto child : adj[node]){
            if (vis[child]==-1){
                vis[child]=color;
                edges[color].push_back(mp[{node,child}]);                
                dfs(child,node);
                color++;
            }
        }
        
        //cout<<"node "<<node<<"\n";
        
        for (int i=0; i<color; i++){
            //cout<<"color "<<i<<"\n";
            vector <int> query;
            for (int j=0; j<color; j++){
                if (j!=i){
                    //cout<<"edges "<<j<<"\n";
                    for (auto x : edges[j]){
                        query.push_back(x);
                    }
                }
            }
            //cout<<query.size()<<' '<<edges[0].size()<<"\n";
            for (int j=1; j<edges[i].size(); j++){
                query.push_back(edges[i][j]);
            }
            
            int mx=0;
            
            int trr=1;
            
            for (auto child : adj[node]){
                if (vis[child]==i && ans[mp[{node,child}]]==0){
                    query.push_back(mp[{node,child}]);
                    int tq = count_common_roads(query);
                    query.pop_back();
                    ans2[mp[{node,child}]]=tq;
                    mx=max(mx,tq);
                }
                else if(trr && vis[child]==i && ans[mp[{node,child}]]==1){
                    trr--;
                    query.push_back(mp[{node,child}]);
                    int tq = count_common_roads(query);
                    query.pop_back();
                    ans2[mp[{node,child}]]=tq;
                    mx=max(mx,tq);
                }
            }
            
            for (auto child : adj[node]){
                if (vis[child]==i && ans[mp[{node,child}]]==0){
                    if (ans2[mp[{node,child}]]==mx){
                        ans[mp[{node,child}]]=1;
                    }
                    else{
                        ans[mp[{node,child}]]=-1;
                    }
                }
            }           
        }
        
        for (int i=0; i<color; i++){
            edges[i].clear();
        }        
    }
    
    
    
    vector <int> submission;
    
    for (int i=0; i<m; i++){
        if (ans[i]==1){
            submission.push_back(i);
            //cout<<i<<' ';
        }
    }
    
    if (submission.size()==n-1){return submission;}
    else{
        //forced abortion
        //int y=0;
        //int x=1/y;
        return submission;
    }
}

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