oj.uz

답안 #1033772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033772 2024-07-25T05:22:27 Z vjudge1 Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 348 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int N_;
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) {
    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){
            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

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

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -