Submission #742177

#	Time	Username	Problem	Language	Result	Execution time	Memory
742177		Ahmed57	Logičari (COCI21_logicari)	C++17	0 / 110	2 ms	2772 KiB

Main

#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>> adj[100001];
stack<int> st;bool ss = 0;
vector<int> cyc;int vis[100001];
void dfs(int i,int j){
    if(vis[i]){
        ss = 1;
        cyc.push_back(i);
        while(st.top()!=i){
            cyc.push_back(st.top());
            st.pop();
        }
        return ;
    }
    vis[i] = 1;
    st.push(i);
    for(auto e:adj[i]){
        if(e.second!=j)dfs(e.first,e.second);
        if(ss)return ;
    }
    if(ss)return ;
    vis[i] = 0;st.pop();
}
bool imp[100001];
pair<int,int> dp[100001][4];
pair<int,int> solve(int i,int typ,int pr){
    if(dp[i][typ]!=make_pair(-1,-1))return dp[i][typ];
    if(typ==0){//it is blue eyed and have blue eyed friend
        pair<int,int> val = {1,1};
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                val.first&=solve(j.first,2,i).first;
                val.second+=solve(j.first,2,i).second;
            }
        }
        return dp[i][typ] = val;
    }if(typ==1){//it is blue eyed and don't have blue eyed friend
        int c = 0 , sz = 0 , su = 0;
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                c+=solve(j.first,2,i).first;
                su+=solve(j.first,2,i).second;
                sz++;
            }
        }
        pair<int,int> ed= {0,1000001};
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                if(c-solve(j.first,2,i).first==sz-1&&solve(j.first,0,i).first){
                    ed.first=1;
                    ed.second = min(ed.second,su-solve(j.first,2,i).second+solve(j.first,0,i).second+1);
                }
            }
        }
        return dp[i][typ] = ed;
    }if(typ==2){//it is not blue eyed but have blue eyed friend
        pair<int,int> val = {1,0};
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                val.first&=solve(j.first,3,i).first;
                val.second+=solve(j.first,3,i).second;
            }
        }
        return dp[i][typ] = val;
    }if(typ==3){//it is not blue eyed and have not blue eyed friend
        int c = 0 , sz = 0 , su = 0;
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                c+=solve(j.first,3,i).first;
                su+=solve(j.first,3,i).second;
                sz++;
            }
        }
        pair<int,int> ed= {0,1000001};
        for(auto j:adj[i]){
            if(!imp[j.first]&&j.first!=pr){
                if(c-solve(j.first,3,i).first==sz-1&&solve(j.first,1,i).first){
                    ed.first=1;
                    ed.second = min(ed.second,su-solve(j.first,3,i).second+solve(j.first,1,i).second);
                }
            }
        }
        return dp[i][typ] = ed;
    }
}
pair<int,int> dp2[100001][4][4][4];
pair<int,int> ee(int i,int first,int togg,int la){
    if(dp2[i][first][togg][la]!=make_pair(-1,-1))return dp2[i][first][togg][la];
    if(la==1){
        
    }
}
signed main(){
    int n;cin>>n;
    for(int i = 0;i<=n;i++){
        dp[i][0] = {-1,-1};
        dp[i][1] = {-1,-1};
        dp[i][2] = {-1,-1};
        dp[i][3] = {-1,-1};
    }
    for(int i = 0;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    dfs(1,-1);
    for(auto j:cyc){
        imp[j] = 1;
    }
    for(auto j:cyc){
        int x= solve(j,0,j).first;
        x= solve(j,1,j).first;
        x= solve(j,2,j).first;
        x= solve(j,3,j).first;
    }
    {
        int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
        for(int i = 1;i<cyc.size()-1;i++){
            
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:113:13: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  113 |         int x= solve(j,0,j).first;
      |             ^
Main.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(int i = 1;i<cyc.size()-1;i++){
      |                       ~^~~~~~~~~~~~~
Main.cpp:119:13: warning: unused variable 'ch' [-Wunused-variable]
  119 |         int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
      |             ^~
Main.cpp:119:49: warning: unused variable 'su' [-Wunused-variable]
  119 |         int ch = solve(cyc[0],0,cyc[0]).first , su = solve(cyc[0],0,cyc[0]).second;
      |                                                 ^~
Main.cpp: In function 'std::pair<int, int> solve(int, int, int)':
Main.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
   87 | }
      | ^
Main.cpp: In function 'std::pair<int, int> ee(int, int, int, int)':
Main.cpp:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40
• Subtask 4: 0 / 50