oj.uz

Submission #1035023

# Submission time Handle Problem Language Result Execution time Memory
1035023 2024-07-26T03:00:39 Z vjudge1 Simurgh (IOI17_simurgh) C++17
19 / 100
 80 ms 4580 KB 
#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){
            vector<int>a,b,c,R2=R;
            for(int i=0;i<V.size();i+=2){
                if(i+1==V.size())
                    break;
                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();
            R=R2;
            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

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:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int i=0;i<V.size();i+=2){
      |                         ~^~~~~~~~~
simurgh.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 if(i+1==V.size())
      |                    ~~~^~~~~~~~~~
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)
      |                      ^

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB correct
2 Correct 1 ms 348 KB correct
3 Correct 50 ms 3272 KB correct
4 Correct 66 ms 4444 KB correct
5 Correct 78 ms 4440 KB correct
6 Correct 47 ms 4440 KB correct
7 Correct 56 ms 4444 KB correct
8 Correct 60 ms 4432 KB correct
9 Correct 77 ms 4444 KB correct
10 Correct 60 ms 4580 KB correct
11 Correct 80 ms 4444 KB correct
12 Correct 63 ms 4432 KB correct
13 Correct 1 ms 348 KB correct
14 Correct 78 ms 4444 KB correct
15 Correct 53 ms 4440 KB correct

Subtask #5
0 / 30.0

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