Submission #1035011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035011		vjudge1	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	604 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int N_;
int indexofr[601][601],deg[601];
void AD(int x,int y){
    R.push_back(indexofr[x][y]);
}
int Q(){ assert(R.size()==N_-1);
    return count_common_roads(R);
}
void die(vector<int>k,int x){
    for(auto i:k)
        AD(x,i);
}
vector<int>ans;
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    N_=n;
    int m=u.size();
    for(int i=0;i<m;i++)
        indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            if(j-i)AD(i,j);
        deg[i]=Q();
        R.clear();
    }
    set<int>st;
    for(int i=0;i<n;i++)
        st.insert(i);
    vector<int>done;
    for(int i=1;i<n;i++){
        int x=0;
        for(int i=0;i<n;i++)
            if(deg[i]==1)x=i;
        R.clear();
        deg[x]=0;
        st.erase(x);
        die(done,x);
        done.push_back(x);
        vector<int>v;
        for(auto i:st)
            v.push_back(i);
        while(v.size()>1){
            assert(R.size()+v.size()==N_-1);
            int origsz=R.size();
            vector<int>a,b,c;
            for(int i=0;i<v.size();i+=2){
                a.push_back(v[i]);
                b.push_back(v[i+1]);
                AD(v[i],v[i+1]);
                if(v.size()-3*a.size()<=1)
                    break;
            }
            for(int i=2*a.size();i<v.size();i++)
                c.push_back(v[i]);
            for(auto i:c)
                AD(x,i);
            for(auto i:a)
                AD(x,i);
            int A=Q();
            for(auto i:a)
                R.pop_back();
            for(auto i:b)
                AD(x,i);
            A-=Q();
            for(auto i:b)
                R.pop_back();
            for(auto i:c)
                R.pop_back();
            for(auto i:b)
                R.pop_back();
            int K=R.size();
            assert(origsz==K);
            if(A<0) die(a,x),
                die(c,x),v=b;
            else if(A)die(b,x),
                die(c,x),v=a;
            else die(a,x),die(b,x),v=c;
        }
        deg[v[0]]--;
        ans.push_back(indexofr[x][v[0]]);
    }
    return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:2:
simurgh.cpp: In function 'int Q()':
simurgh.cpp:10:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   10 | int Q(){ assert(R.size()==N_-1);
      |                 ~~~~~~~~^~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:46:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |             assert(R.size()+v.size()==N_-1);
      |                    ~~~~~~~~~~~~~~~~~^~~~~~
simurgh.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int i=0;i<v.size();i+=2){
      |                         ~^~~~~~~~~
simurgh.cpp:56:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(int i=2*a.size();i<v.size();i++)
      |                                  ~^~~~~~~~~
simurgh.cpp:63:22: warning: unused variable 'i' [-Wunused-variable]
   63 |             for(auto i:a)
      |                      ^
simurgh.cpp:68:22: warning: unused variable 'i' [-Wunused-variable]
   68 |             for(auto i:b)
      |                      ^
simurgh.cpp:70:22: warning: unused variable 'i' [-Wunused-variable]
   70 |             for(auto i:c)
      |                      ^
simurgh.cpp:72:22: warning: unused variable 'i' [-Wunused-variable]
   72 |             for(auto i:b)
      |                      ^

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