Submission #140157

#	Time	Username	Problem	Language	Result	Execution time	Memory
140157		davitmarg	Simurgh (IOI17_simurgh)	C++17	0 / 100	24 ms	3716 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)
{
	if(ans.size()==n-1)
		return;
    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;
	if(ans.size()==n-1)
		return;
    int rad=id[MP(p,v)];
	//cout<<"from "<<v<<endl;
    random_shuffle(all(backs[v]));
	int qanak=0;
    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]);
			qanak++;
		}
        else if(newcnt<cnt)
        {
            answer(rad);
			qanak++;
            break;
        }
		if(ans.size()==n-1)
			return;
    }
	backs[v].clear();
	if(qanak==0)
		answer(rad);
}


vector<int> find_roads(int N,vector<int> U,vector<int> V)
{
	srand(6446546);
    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

/*


7 21
2 0
0 1
5 2
2 6
1 3
3 0
6 0
4 5
3 2
4 0
1 4
0 5
4 3
4 6
6 1
2 1
5 3
2 4
5 6
5 1
6 3

6 9
0 1
1 2
2 0
2 3
3 4
3 5
4 5
0 4
1 5


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:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans.size()==n-1)
     ~~~~~~~~~~^~~~~
simurgh.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[v].size();i++)
                 ~^~~~~~~~~~~~
simurgh.cpp:92:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(p==-1)
     ^~
simurgh.cpp:94:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ans.size()==n-1)
  ^~
simurgh.cpp:94:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans.size()==n-1)
     ~~~~~~~~~~^~~~~
simurgh.cpp:100:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<backs[v].size();i++)
                 ~^~~~~~~~~~~~~~~~
simurgh.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ans.size()==n-1)
      ~~~~~~~~~~^~~~~

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