Submission #1120672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120672		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	2083 ms	51096 KiB

kovanice

// Ali
 
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 3e5+23, inf = 2e9, LG = 19,pr = 31;
int val[sze];
vector<int> graph[sze];
set<pii> path;
int used[sze];
// bool ff=true;
// int qir = 1b ;
void dfs(int node,int x){
    
    // if( || !ff){
    //     ff=false;
    //     return;
    // }
    // used[node]=1;
    // path.pb({x,node});
    path.ins({x,node});
    for(auto v:graph[node]){
        dfs(v,x-1);
    }
}
struct lan{
    vector<int> parent;
    vector<int> sz;
    lan(int n){
        parent.resize(n+23);
        iota(all(parent),0);
        sz.resize(n+23,1);
    }

    int root(int a){
        if(parent[a]==a){
            return a;
        }
        return parent[a]=root(parent[a]);
    }
    void unite(int a,int b){
        int x = root(a);
        int y = root(b);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            parent[y]=x;
        }
    }
};
void fast(){
    int n,m,qq;
    cin>>n>>m>>qq;
    vector<pair<pii,char>> q;
    bool flag=false;
    while(qq--){
        string s;
        cin>>s;
        string a="";
        string b="";
        char op;
        for(auto v:s){
            if(v=='<' || v=='='){
                op = v;
                swap(a,b);
            }   
            else{
                a+=v;
            }
        }
        swap(a,b);
        q.pb({{stoll(a),stoll(b)},op});
        // cout<<a<<" "<<op<<" "<<b<<endl;
        if(op=='<' && !flag){
            flag=true;
        }
    }
    lan dsu(m+23);
    if(flag){
        vector<int> fk(m+23,0);
        set<int> lst;
        vector<pair<int,int>> fuk;
        for(auto [vv,op]:q){
            int a = vv.first;
            int b = vv.second;
            if(op=='='){
                dsu.unite(a,b);
            }
            else{
                // val[a]=1;
                // val[b]=2;
                // a<b ise ne olucak ?
                // en boyuk hansidi o lazim
                fuk.pb({a,b});
            }
        }
        set<pair<int,int>> gg;
        for(auto &v:fuk){
            v.first =dsu.root(v.first);
            v.second =dsu.root(v.second);
            lst.ins(v.first);
            lst.ins(v.second);
        }
        for(auto [k,v]:fuk){
            int a = dsu.root(k);
            if(a!=k && lst.find(k)!=lst.end()){
                lst.erase(k);
                // cout<<"silk "<<k<<endl;
            }
            int b = dsu.root(v);
            if(b!=v && lst.find(v)!=lst.end()){
                // cout<<" silv"<<v<<endl;
                lst.erase(v);
            }

            if(gg.find({b,a})==gg.end()){
                gg.ins({b,a});
                graph[b].pb(a);
            }
        }
        for(auto v:fuk){
            int a = dsu.root(v.first);
            // cout<<v.first<<" ,"<<v.second<<endl;
            if(lst.find(a)!=lst.end()){
                lst.erase(lst.find(a));
            }
        }
        // for(auto v:lst){
        //     cout<<v<<" ";
        // }cout<<endl;
        if(!lst.empty()){
            for(auto root:lst){
                // int a = *lst.begin();
                // cout<<"enbuyuk : "<<a<<endl;
                path.clear();
                dfs(root,n);
                // ff=true;
                // cout<<root<<" : \n";
                // for(auto v:path) cout<<v.first<<" "<<v.second<<"\n";cout<<endl;
                // assert(path.size()<=n);
                // sort(all(path));
                // reverse(all(path));
                int x =n;
                vector<pair<int,int>> bb;
                while(!path.empty()){
                    
                    // bb.pb({v,k});
                    auto it = path.lower_bound({x,-1});
                    if(it==path.end()){
                        break;
                    }
                    x--;
                    path.erase(it);
                    bb.pb(*it);

                    if(x==0){
                        for(auto [aq,gq]:bb){
                            val[gq]=aq;
                        }
                        bb.clear();
                        x=n;
                    }
                }
                /*
                2 5 3
                1<2
                3<2

                3=4
                */
                // cout<<x<<endl;
                if(x==0){
                }
            }
        }




        for(int i =1;i<=m;i++){
            fk[dsu.root(i)]|=val[i];
        }
        for(int i =1;i<=m;i++){
            val[i]=fk[dsu.root(i)];
        }
    }

    for(int i=1;i<=m;i++){
        if(val[i]<=0){
            cout<<"?"<<endl;
        }
        else{
            cout<<"K"<<val[i]<<endl;
        }
    }
}
  
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'void fast()':
kovanice.cpp:83:9: warning: 'op' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |         if(op=='<' && !flag){
      |         ^~

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