oj.uz

Submission #1033737

# Submission time Handle Problem Language Result Execution time Memory
1033737 2024-07-25T04:43:21 Z vjudge1 Simurgh (IOI17_simurgh) C++17
51 / 100
 711 ms 8704 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];
bitset<501>vis;
vector<int>origintree;
int N_,K_;
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);
        origintree.push_back(indexofr[n][i]);
    }
}
void mergethese(set<int>st){
    tis.reset();
    for(int i=0;i<U.size();i++){
        int a=U[i],b=V[i];
        if(!st.count(a)||!st.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(st.count(a)||st.count(b))
            continue;
        if(tis.merge(a,b))
            R.push_back(i);
    }
}
void specialcheck(int n){

}
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]);
    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;
    int D=prev(mp.end())->first;
    if(mp.size()==2){
        for(auto i:C)
            TIS2.merge(U[i],V[i]),
            ans.push_back(i);
    } else {
        int cond=1;
        if(subtree[n].size()==1)
            cond=1;
        else {
            for(int i=0;i<U.size();i++){
                int a=U[i],b=V[i];
                if(a-n&&b-n&&subtree[n].count(a)!=subtree[n].count(b)){
                    R.push_back(i);
                    if(query()+!(count(ans.begin(),ans.end(),i))>D)
                        cond=0;
                    break;
                }
            }
        }
        if(cond) for(auto i:C)
            TIS2.merge(U[i],V[i]),
            ans.push_back(i);
    }
}
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();
    if(m==n-1){
        ans.resize(m);
        iota(ans.begin(),ans.end(),0);
        return ans;
    }
    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);
    findstuff(0,0);
    return ans;
}

Compilation message

simurgh.cpp: In member function 'bool dsu::merge(int, int)':
simurgh.cpp:23:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   23 |         return par[a]=b;
      |                ~~~~~~^~
simurgh.cpp: In function 'void mergethese(std::set<int>)':
simurgh.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
simurgh.cpp:52:18: 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=0;i<U.size();i++){
      |                 ~^~~~~~~~~
simurgh.cpp: In function 'void findstuff(int, int)':
simurgh.cpp:92:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for(int i=0;i<U.size();i++){
      |                         ~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 604 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 1 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 1 ms 600 KB correct
10 Correct 0 ms 716 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 0 ms 604 KB correct
13 Correct 0 ms 604 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 604 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 1 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 1 ms 600 KB correct
10 Correct 0 ms 716 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 0 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 860 KB correct
17 Correct 4 ms 940 KB correct
18 Correct 2 ms 908 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 4 ms 724 KB correct
22 Correct 3 ms 860 KB correct
23 Correct 3 ms 856 KB correct
24 Correct 3 ms 856 KB correct
25 Correct 1 ms 600 KB correct
26 Correct 2 ms 892 KB correct
27 Correct 3 ms 860 KB correct
28 Correct 2 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 3 ms 860 KB correct
31 Correct 3 ms 916 KB correct
32 Correct 3 ms 860 KB correct
33 Correct 3 ms 860 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 604 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 1 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 1 ms 600 KB correct
10 Correct 0 ms 716 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 0 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 860 KB correct
17 Correct 4 ms 940 KB correct
18 Correct 2 ms 908 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 4 ms 724 KB correct
22 Correct 3 ms 860 KB correct
23 Correct 3 ms 856 KB correct
24 Correct 3 ms 856 KB correct
25 Correct 1 ms 600 KB correct
26 Correct 2 ms 892 KB correct
27 Correct 3 ms 860 KB correct
28 Correct 2 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 3 ms 860 KB correct
31 Correct 3 ms 916 KB correct
32 Correct 3 ms 860 KB correct
33 Correct 3 ms 860 KB correct
34 Correct 689 ms 4000 KB correct
35 Correct 674 ms 3672 KB correct
36 Correct 453 ms 3452 KB correct
37 Correct 33 ms 2396 KB correct
38 Correct 680 ms 3676 KB correct
39 Correct 593 ms 3632 KB correct
40 Correct 462 ms 3416 KB correct
41 Correct 711 ms 4020 KB correct
42 Correct 695 ms 3740 KB correct
43 Correct 335 ms 3104 KB correct
44 Correct 250 ms 2656 KB correct
45 Correct 320 ms 2896 KB correct
46 Correct 230 ms 2652 KB correct
47 Correct 88 ms 1992 KB correct
48 Correct 10 ms 1368 KB correct
49 Correct 32 ms 2140 KB correct
50 Correct 97 ms 2288 KB correct
51 Correct 304 ms 2732 KB correct
52 Correct 259 ms 2896 KB correct
53 Correct 235 ms 2648 KB correct
54 Correct 339 ms 2776 KB correct
55 Correct 351 ms 3164 KB correct
56 Correct 336 ms 3184 KB correct
57 Correct 340 ms 3160 KB correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB correct
2 Correct 0 ms 604 KB correct
3 Correct 0 ms 604 KB correct
4 Correct 0 ms 604 KB correct
5 Correct 0 ms 604 KB correct
6 Correct 1 ms 604 KB correct
7 Correct 0 ms 604 KB correct
8 Correct 0 ms 604 KB correct
9 Correct 1 ms 600 KB correct
10 Correct 0 ms 716 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 0 ms 604 KB correct
13 Correct 0 ms 604 KB correct
14 Correct 5 ms 860 KB correct
15 Correct 5 ms 860 KB correct
16 Correct 5 ms 860 KB correct
17 Correct 4 ms 940 KB correct
18 Correct 2 ms 908 KB correct
19 Correct 4 ms 856 KB correct
20 Correct 4 ms 860 KB correct
21 Correct 4 ms 724 KB correct
22 Correct 3 ms 860 KB correct
23 Correct 3 ms 856 KB correct
24 Correct 3 ms 856 KB correct
25 Correct 1 ms 600 KB correct
26 Correct 2 ms 892 KB correct
27 Correct 3 ms 860 KB correct
28 Correct 2 ms 860 KB correct
29 Correct 1 ms 860 KB correct
30 Correct 3 ms 860 KB correct
31 Correct 3 ms 916 KB correct
32 Correct 3 ms 860 KB correct
33 Correct 3 ms 860 KB correct
34 Correct 689 ms 4000 KB correct
35 Correct 674 ms 3672 KB correct
36 Correct 453 ms 3452 KB correct
37 Correct 33 ms 2396 KB correct
38 Correct 680 ms 3676 KB correct
39 Correct 593 ms 3632 KB correct
40 Correct 462 ms 3416 KB correct
41 Correct 711 ms 4020 KB correct
42 Correct 695 ms 3740 KB correct
43 Correct 335 ms 3104 KB correct
44 Correct 250 ms 2656 KB correct
45 Correct 320 ms 2896 KB correct
46 Correct 230 ms 2652 KB correct
47 Correct 88 ms 1992 KB correct
48 Correct 10 ms 1368 KB correct
49 Correct 32 ms 2140 KB correct
50 Correct 97 ms 2288 KB correct
51 Correct 304 ms 2732 KB correct
52 Correct 259 ms 2896 KB correct
53 Correct 235 ms 2648 KB correct
54 Correct 339 ms 2776 KB correct
55 Correct 351 ms 3164 KB correct
56 Correct 336 ms 3184 KB correct
57 Correct 340 ms 3160 KB correct
58 Correct 1 ms 600 KB correct
59 Correct 0 ms 604 KB correct
60 Incorrect 199 ms 8704 KB WA in grader: NO
61 Halted 0 ms 0 KB -