Submission #439209

#	Time	Username	Problem	Language	Result	Execution time	Memory
439209		fadi57	KOVANICE (COI15_kovanice)	C++14	100 / 100	637 ms	39364 KiB

kovanice

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int mx=3e5+10;
typedef long long ll;
const int mod=1e9+7;
int inf=1e9+10;
int n,m,v;
int par[mx],siz[mx];
vector<int>adj[2][mx];
int dp[2][mx];
void init(){

for(int i=1;i<=m;i++){

    par[i]=i;siz[i]=1;
}

}
 int fin(int a){

  if(par[a]!=a){

    return par[a]=fin(par[a]);
  }else{

    return a;
   }



  }
 void uni(int a,int b){

       int aa=fin(a);
       int bb=fin(b);

      if(aa!=bb){

        if(siz[aa]>siz[bb]){swap(aa,bb);}

        par[aa]=bb;
        siz[bb]+=siz[aa];
      }

 return;



  }

  int smaller[mx];int bigger[mx];
int vis[mx];
  void solve(int node){
      if(vis[node]){return;}
     vis[node]=1;

     for(auto it:adj[0][node]){
     solve(it);
        bigger[fin(node)]=max(bigger[node],bigger[it]+1);
     }
  return;
   }
     void solve2(int node){
      if(vis[node]){return;}
     vis[node]=1;
  //cout<<node<<" ";
     for(auto it:adj[1][node]){
     solve2(it);
        smaller[fin(node)]=max(smaller[node],smaller[it]+1);
     }


  return;
   }
 int main(){
 cin>>n>>m>>v;

 init();
vector<pair<int,int>>edges;
   for(int i =0;i<v;i++){
    int a,b;char c;
    cin>>a>>c>>b;

    if(c=='='){

        uni(a,b);
    }else{
  edges.push_back({a,b});

    /*adj[0][fin(a)].push_back(fin(b));
     adj[1][fin(b)].push_back(fin(a));
     */
     }

   }
for(auto it:edges){
        int a=it.first;
int b=it.second;
     adj[0][fin(a)].push_back(fin(b));
       adj[1][fin(b)].push_back(fin(a));

}
   for(int i=1;i<=m;i++){
    if(i==par[i]&&vis[i]==0){
    solve(i);

    }

   }
   /*
   solve2(4);
   cout<<endl;
   cout<<smaller[4];
   */
   memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++){
    if(i==par[i]&&vis[i]==0){
      solve2(i);
  //cout<<vis[i]<<" ";
    }

   }
  // cout<<"\n";
    for(int i=1;i<=m;i++){
   int me=fin(i);

   if(bigger[me]+smaller[me]+1==n){
    cout<<"K"<<smaller[me]+1;
   }else{
   cout<<"?";
    }
    cout<<"\n";
   }

 }

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