oj.uz

Submission #439209

# Submission time Handle Problem Language Result Execution time Memory
439209 2021-06-29T11:43:46 Z fadi57 KOVANICE (COI15_kovanice) C++14
100 / 100
 637 ms 39364 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15564 KB Output is correct
2 Correct 13 ms 15632 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 22292 KB Output is correct
2 Correct 174 ms 23560 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 17408 KB Output is correct
2 Correct 76 ms 18160 KB Output is correct
3 Correct 72 ms 18244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 31292 KB Output is correct
2 Correct 512 ms 33804 KB Output is correct
3 Correct 486 ms 33628 KB Output is correct
4 Correct 629 ms 38436 KB Output is correct
5 Correct 637 ms 39364 KB Output is correct