oj.uz

답안 #1033558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033558 2024-07-25T03:54:40 Z vjudge1 Simurgh (IOI17_simurgh) C++17
13 / 100
 3000 ms 1112 KB 
#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>R;
int query(){
    return count_common_roads(R);
}
vector<int>U,V;
set<int>subtree[501];
vector<int>AADJ[10010],adj[501];
int indexofr[501][501],wenow[100100];
bitset<501>vis;
int N_;
struct dsu{
    int par[501];
    int abp(int n){
        return par[n]?par[n]=abp(par[n]):n;
    }
    bool merge(int a,int b){
        a=abp(a+1),b=abp(b+1);
        if(a==b) return 0;
        return par[a]=b;
    }
    void reset(){
        memset(par,0,sizeof par);
    }
} tis, TIS2;
/*void gendfstree(int n){
    vis[n]=1;
    subtree[n].insert(n);
    for(auto i:AADJ[n]){
        if(vis[i])continue;
        gendfstree(i);
        for(auto j:subtree[i])
            subtree[n].insert(j);
        adj[i].push_back(n);
        adj[n].push_back(i);
    }
}
void mergethese(set<int>v,set<int>v2,int p){
    tis.reset();
    for(int i=0;i<U.size();i++){
        int a=U[i],b=V[i];
        if(!v.count(a)||!v.count(b))
            continue;
        if(tis.merge(a,b))
            R.push_back(i);
    }
    tis.reset();
    for(int i=0;i<U.size();i++){
        int a=U[i],b=V[i];
        if(v2.count(a)||v2.count(b))
            continue;
        if(tis.merge(a,b))
            R.push_back(i);
    }
    for(int i=0;i<U.size();i++){
        int a=U[i],b=V[i];
        if(v.count(a)||v.count(b)||a==p||b==p)
            continue;
        if(tis.merge(a,b))
            R.push_back(i);
    }
}
vector<int>ans;
void findstuff(int n,int p){
    for(auto i:adj[n])
        if(i-p)findstuff(i,n);
    if(!n)return;
    vector<int>R2=R;
    R.clear();
    mergethese(subtree[n],subtree[p],p);
    vector<int>specrod;
    for(auto i:AADJ[n])
        if(subtree[i].size()>subtree[n].size())
            specrod.push_back(indexofr[i][n]);
    map<int,vector<int>>mp;
    for(auto i:specrod){
        R.push_back(i);
        mp[query()].push_back(i);
        R.pop_back();
    }
    vector<int>C=prev(mp.end())->second;
    if(mp.size()==2){
        for(auto i:C)
            TIS2.merge(U[i],V[i]),
            ans.push_back(i),wenow[i]=2;
    } else if(subtree[n].size()==1||specialcheck(R2,*mp.begin(),n)) {
        for(auto i:C)
            TIS2.merge(U[i],V[i]),
            ans.push_back(i),wenow[i]=2;
    }
    for(auto i:AADJ[n])
        wenow[i]=max(wenow[i],1);
}*/
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
    /*U=u;
    V=v;
    N_=n;
    int m=u.size();
    for(int i=0;i<m;i++)
        AADJ[u[i]].push_back(v[i]),
        AADJ[v[i]].push_back(u[i]),
        indexofr[u[i]][v[i]]=indexofr[v[i]][u[i]]=i;
    gendfstree(0);*/
    int C=u.size();
    for(int i=0;i<1<<C;i++){
        if(__builtin_popcount(i)!=n-1)continue;
        tis.reset();
        vector<int>V;
        for(int j=0;j<u.size();j++)
            if(i&1<<j) V.push_back(j);
        int bad=0;
        for(auto i:V)
            if(!tis.merge(u[i],v[i]))
                bad=1;
        if(bad)continue;
        if(count_common_roads(V)==n-1)
            return V;
    }
}

Compilation message

simurgh.cpp: In member function 'bool dsu::merge(int, int)':
simurgh.cpp:22:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   22 |         return par[a]=b;
      |                ~~~~~~^~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int j=0;j<u.size();j++)
      |                     ~^~~~~~~~~
simurgh.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB correct
2 Correct 16 ms 604 KB correct
3 Correct 17 ms 720 KB correct
4 Correct 1 ms 604 KB correct
5 Correct 1 ms 604 KB correct
6 Correct 2 ms 1112 KB correct
7 Correct 1 ms 856 KB correct
8 Correct 1 ms 604 KB correct
9 Correct 1 ms 652 KB correct
10 Correct 1 ms 716 KB correct
11 Correct 0 ms 604 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 8 ms 600 KB correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB correct
2 Correct 16 ms 604 KB correct
3 Correct 17 ms 720 KB correct
4 Correct 1 ms 604 KB correct
5 Correct 1 ms 604 KB correct
6 Correct 2 ms 1112 KB correct
7 Correct 1 ms 856 KB correct
8 Correct 1 ms 604 KB correct
9 Correct 1 ms 652 KB correct
10 Correct 1 ms 716 KB correct
11 Correct 0 ms 604 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 8 ms 600 KB correct
14 Execution timed out 3031 ms 600 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB correct
2 Correct 16 ms 604 KB correct
3 Correct 17 ms 720 KB correct
4 Correct 1 ms 604 KB correct
5 Correct 1 ms 604 KB correct
6 Correct 2 ms 1112 KB correct
7 Correct 1 ms 856 KB correct
8 Correct 1 ms 604 KB correct
9 Correct 1 ms 652 KB correct
10 Correct 1 ms 716 KB correct
11 Correct 0 ms 604 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 8 ms 600 KB correct
14 Execution timed out 3031 ms 600 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 600 KB correct
2 Execution timed out 3053 ms 604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB correct
2 Correct 16 ms 604 KB correct
3 Correct 17 ms 720 KB correct
4 Correct 1 ms 604 KB correct
5 Correct 1 ms 604 KB correct
6 Correct 2 ms 1112 KB correct
7 Correct 1 ms 856 KB correct
8 Correct 1 ms 604 KB correct
9 Correct 1 ms 652 KB correct
10 Correct 1 ms 716 KB correct
11 Correct 0 ms 604 KB correct
12 Correct 1 ms 604 KB correct
13 Correct 8 ms 600 KB correct
14 Execution timed out 3031 ms 600 KB Time limit exceeded
15 Halted 0 ms 0 KB -