oj.uz

Submission #227390

# Submission time Handle Problem Language Result Execution time Memory
227390 2020-04-27T09:34:48 Z PedroBigMan Simurgh (IOI17_simurgh) C++14
13 / 100
 3000 ms 384 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include "simurgh.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
#define REP(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 100000000
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll N,M; vector<pl> ed; vector<ll> ans;

class Graph
{
    public:
    ll N;
    vector<vector<ll> > adj; 
    vector<ll> visited; //for DFS/BFS
    vector<ll> current; //for CC
    vector<bool> c; //for Bip
    bool bip; //for Bip
    
    Graph() {ll N=0LL;}
    
    Graph(vector<vector<ll> > ad)
    {
        adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false); c.pb(-1);}
    }
    
    void Reset()
    {
        REP(i,0,N) {visited[i]=false;}
        current.clear();
    }
    
    void DFS(ll s) 
    {
        if(visited[s]) {return;}
        visited[s]=true;
        current.pb(s); //only needed for CC
        REP(i,0,adj[s].size())
        {
            if(!visited[adj[s][i]]) {c[adj[s][i]]=(c[s]+1)%2; DFS(adj[s][i]);}
            else if(c[adj[s][i]]==c[s]) {bip=false;}
        }
        return;
    }
    
    bool Connected()
    {
        Reset();
        DFS(0);
        REP(i,0,N) {if(!visited[i]) {return false;}}
        return true;
    }
    
    vector<ll> BFS(ll s)
    {
        vector<ll> distance; REP(i,0,N) {distance.pb(INF);}
        REP(i,0,N) {visited[i]=false;}
        distance[s]=0; visited[s]=true;
        deque<ll> d; d.pb(s); ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(!visited[adj[cur][i]]) 
                {
                    visited[adj[cur][i]]=true; 
                    d.pb(adj[cur][i]); 
                    distance[adj[cur][i]]=distance[cur]+1;
                }
            }
        }
        return distance;
    }
    
    vector<pl> BFS_MS(vector<ll> sn) //multi-sourced BFS, ans[i].ff=d(i,starting nodes), ans[i].ss=starting node closer to i
    {
        ll K=sn.size();
        vector<pl> distance; REP(i,0,N) {distance.pb(mp(INF,-1LL));}
        REP(i,0,N) {visited[i]=false;}
        REP(i,0,K) {distance[sn[i]]=mp(0LL,sn[i]); visited[sn[i]]=true;}
        deque<ll> d; REP(i,0,K) {d.pb(sn[i]);} ll cur;
        while(!d.empty())
        {
            cur=d.front(); d.pop_front();
            REP(i,0,adj[cur].size())
            {
                if(visited[adj[cur][i]]) {continue;}
                visited[adj[cur][i]]=true; 
                d.pb(adj[cur][i]); 
                distance[adj[cur][i]].ff=distance[cur].ff+1;
                distance[adj[cur][i]].ss=distance[cur].ss;
            }
        }
        return distance;
    }
    
    vector<vector<ll> > CC()
    {
        ll fi=0; ll missing=N; REP(i,0,N) {visited[i]=false;}
        vector<vector<ll> > ans;
        while(missing>0)
        {
            REP(i,fi,N) {if(!visited[i]) {fi=i; break;}}
            current.clear();
            DFS(fi);
            ans.pb(current);
            missing-=current.size();
        }
        return ans;
    }
    
    vector<Graph> CCG()
    {
        vector<Graph> ans;
        vector<vector<ll> > CC=(*this).CC();
        unordered_map<ll,ll> m;vector<ll> xx; vector<vector<ll> > ad;
        REP(cc,0,CC.size()) 
        {
            m.clear(); 
            ad.clear(); 
            ll NN=CC[cc].size();
            REP(i,0,NN) {ad.pb(xx);}
            REP(i,0,NN) {m[CC[cc][i]]=i;}
            ll a,b;
            REP(i,0,NN)
            {
                a=CC[cc][i];
                REP(j,0,adj[a].size()) {b=adj[a][j]; ad[i].pb(m[b]);}
            }
            Graph H(ad);
            ans.pb(H);
        }
        return ans;
    }
    
    bool Bip()
    {
        c[0]=0; 
        bip=true;
        DFS(0);
        if(bip) {return true;}
        else {return false;}
    }
    
    bool Eulerian()
    {
        REP(i,0,N) {if(adj[i].size()%2!=0) {return false;}}
        return true;
    }
};

void f(vector<int> a, ll c)
{
    if(!ans.empty()) {return;}
    if(a.size()==N-1)
    {
        vector<vector<ll> > adj; vector<ll> xx; REP(i,0,N) {adj.pb(xx);}
        REP(i,0,a.size()) 
        {
            adj[ed[a[i]].ff].pb(ed[a[i]].ss);
            adj[ed[a[i]].ss].pb(ed[a[i]].ff);
        }
        Graph G(adj);    
        if(!G.Connected()) {return;}
        int common = count_common_roads(a);
        if(common==N-1) {ans=a; return;}
    }
    else
    {
        REP(i,c,M) 
        {
            a.pb(i); f(a,i+1); a.pop_back();
        }
    }
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) 
{
	N=(ll) n; M=u.size();
    REP(i,0,M) {ed.pb(mp(u[i],v[i]));}
    vector<int> em;
    f(em,0LL);
    return ans;
}

Compilation message

simurgh.cpp: In constructor 'Graph::Graph()':
simurgh.cpp:41:17: warning: unused variable 'N' [-Wunused-variable]
     Graph() {ll N=0LL;}
                 ^
simurgh.cpp: In function 'void f(std::vector<int>, ll)':
simurgh.cpp:177:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(a.size()==N-1)
        ~~~~~~~~^~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 384 KB correct
2 Correct 34 ms 384 KB correct
3 Correct 88 ms 256 KB correct
4 Correct 6 ms 384 KB correct
5 Correct 5 ms 256 KB correct
6 Correct 9 ms 256 KB correct
7 Correct 5 ms 384 KB correct
8 Correct 5 ms 352 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 5 ms 256 KB correct
12 Correct 6 ms 256 KB correct
13 Correct 95 ms 376 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 384 KB correct
2 Correct 34 ms 384 KB correct
3 Correct 88 ms 256 KB correct
4 Correct 6 ms 384 KB correct
5 Correct 5 ms 256 KB correct
6 Correct 9 ms 256 KB correct
7 Correct 5 ms 384 KB correct
8 Correct 5 ms 352 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 5 ms 256 KB correct
12 Correct 6 ms 256 KB correct
13 Correct 95 ms 376 KB correct
14 Execution timed out 3073 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 384 KB correct
2 Correct 34 ms 384 KB correct
3 Correct 88 ms 256 KB correct
4 Correct 6 ms 384 KB correct
5 Correct 5 ms 256 KB correct
6 Correct 9 ms 256 KB correct
7 Correct 5 ms 384 KB correct
8 Correct 5 ms 352 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 5 ms 256 KB correct
12 Correct 6 ms 256 KB correct
13 Correct 95 ms 376 KB correct
14 Execution timed out 3073 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB correct
2 Incorrect 783 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 384 KB correct
2 Correct 34 ms 384 KB correct
3 Correct 88 ms 256 KB correct
4 Correct 6 ms 384 KB correct
5 Correct 5 ms 256 KB correct
6 Correct 9 ms 256 KB correct
7 Correct 5 ms 384 KB correct
8 Correct 5 ms 352 KB correct
9 Correct 5 ms 384 KB correct
10 Correct 8 ms 256 KB correct
11 Correct 5 ms 256 KB correct
12 Correct 6 ms 256 KB correct
13 Correct 95 ms 376 KB correct
14 Execution timed out 3073 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -