oj.uz

Submission #1033763

# Submission time Handle Problem Language Result Execution time Memory
1033763 2024-07-25T05:09:34 Z vjudge1 Simurgh (IOI17_simurgh) C++17
0 / 100
 0 ms 348 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int indexofr[501][501],deg[501];
void AD(int x,int y){
    R.push_back(indexofr[x][y]);
}
int Q(){
    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) {
    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;
            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()-2*a.size()-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();
            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

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int i=0;i<v.size();i+=2){
      |                         ~^~~~~~~~~
simurgh.cpp:52:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for(int i=2*a.size();i<v.size();i++)
      |                                  ~^~~~~~~~~
simurgh.cpp:59:22: warning: unused variable 'i' [-Wunused-variable]
   59 |             for(auto i:a)
      |                      ^
simurgh.cpp:64:22: warning: unused variable 'i' [-Wunused-variable]
   64 |             for(auto i:b)
      |                      ^
simurgh.cpp:66:22: warning: unused variable 'i' [-Wunused-variable]
   66 |             for(auto i:c)
      |                      ^

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

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