Submission #140123

#	Time	Username	Problem	Language	Result	Execution time	Memory
140123		davitmarg	Simurgh (IOI17_simurgh)	C++17	0 / 100	2 ms	376 KiB

simurgh

//DM
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
//#define death
#ifndef death
    #include "simurgh.h"
#endif // death
#define LL long long
#define mod 1000000007ll
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

#ifdef death

int count_common_roads(vector<int> a){
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<"!\n";
    int ans;
    cin>>ans;
    return ans;
}


#endif //death

int n,m,used[502],cnt,fnd[502],tin[502],timer;
vector<int> g[502];
map<pair<int,int>,int> id;
vector<int> backs[502],ans,print;
pair<int,int> edge[502];

void answer(int a)
{
    if(fnd[a])
        return;
    fnd[a]=1;
    ans.PB(a);

}

int get(int old,int nw)
{
    vector<int> x=print;
    for(int i=0;i<x.size();i++)
        if(x[i]==old)
            x[i]=nw;
    return count_common_roads(x);
}

void dfs1(int v,int p=-1)
{
    used[v]=1;
	tin[v]=++timer;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i];
        if(to==p)
            continue;
        if(used[to])
        {
            backs[v].PB(id[MP(v,to)]);
            continue;
        }
        print.PB(id[MP(v,to)]);
        dfs1(to,v);
    }
}

void dfs(int v,int p=-1)
{
    used[v]=1;
    for(int i=0;i<g[v].size();i++)
    {
        int to=g[v][i];
        if(used[to])
            continue;
        dfs(to,v);
    }

    if(p==-1)
        return;
    int rad=id[MP(p,v)];
	//cout<<"from "<<v<<endl;
    random_shuffle(all(backs[v]));
    for(int i=0;i<backs[v].size();i++)
    {
		int a,b;
		a=edge[backs[v][i]].first;
		b=edge[backs[v][i]].second;
		if(min(tin[a],tin[b])>=tin[v])
			continue;
		backs[p].PB(backs[v][i]);
        int newcnt=get(rad,backs[v][i]);
        if(newcnt>cnt)
            answer(backs[v][i]);
        else if(newcnt<cnt)
        {
            answer(rad);
            break;
        }
    }

}


vector<int> find_roads(int N,vector<int> U,vector<int> V)
{
    n=N;
    m=U.size();
    for(int i=0;i<m;i++)
    {
        int a=U[i];
        int b=V[i];
		edge[i]=MP(a,b);
        id[MP(a,b)]=id[MP(b,a)]=i;
        g[a].PB(b);
        g[b].PB(a);
    }
    int start=(rand()%n);
    dfs1(start);
    for(int i=0;i<n;i++)
        used[i]=0;

    cnt=count_common_roads(print);

    dfs(start);
    return ans;
}


#ifdef death

int main()
{
    int N,M;
    vector<int> U,V;
    cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin>>a>>b;
        U.PB(a);
        V.PB(b);
    }
    vector<int> ANS=find_roads(N,U,V);
    cout<<"!!!!\n";
    for(int i=0;i<ANS.size();i++)
    {
        cout<<U[ANS[i]]<<":"<<V[ANS[i]]<<endl;
    }
	return 0;
}

#endif // death

/*


4 6
0 1
0 2
0 3
1 2
1 3
2 3





*/

Compilation message (stderr)

simurgh.cpp: In function 'int get(int, int)':
simurgh.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<x.size();i++)
                 ~^~~~~~~~~
simurgh.cpp: In function 'void dfs1(int, int)':
simurgh.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
simurgh.cpp: In function 'void dfs(int, int)':
simurgh.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
simurgh.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<backs[v].size();i++)
                 ~^~~~~~~~~~~~~~~~

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