oj.uz

답안 #27445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27445 2017-07-12T15:35:16 Z gs14004 KOVANICE (COI15_kovanice) C++14
100 / 100
 503 ms 66824 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<lint, lint> pi;
 
int n, m, v;
 
struct disj{
    int pa[300005], size[300005];
    void init(int n){
        for(int i=1; i<=n; i++) pa[i] = i, size[i] = 1;
    }
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
    int getsize(int x){
        return size[find(x)];
    }
    bool uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        pa[q] = p; size[p] += size[q];
        return 1;
    }
}disj;
 
vector<pi> edgs;
vector<int> g1[300005], g2[300005], g3[300005];
 
int piv;
int comp[300005];
int ret[300005];
 
void dfs(int x, int p){
    if(comp[x]) return;
    comp[x] = p;
    for(auto &i : g1[x]){
        dfs(i, p);
    }
}
 
vector<pi> cnd;
int dp1[300005], dp2[300005];
 
int f(int x){
    if(~dp1[x]) return dp1[x];
    int ret = 0;
    for(auto &i : g2[x]){
        ret = max(ret, f(i));
    }
    return dp1[x] = ret + 1;
}
 
int g(int x){
    if(~dp2[x]) return dp2[x];
    int ret = 0;
    for(auto &i : g3[x]){
        ret = max(ret, g(i));
    }
    return dp2[x] = ret + 1;
}
 
void solve(int s, int e){
    for(int i=s; i<=e; i++){
        int t = cnd[i].second;
        int p1 = f(t), p2 = g(t);
        if(p1 + p2 == n+1) ret[t] = p2;
        else ret[t] = -1;
    }
}
 
int main(){
    scanf("%d %d %d",&n,&m,&v);
    disj.init(m);
    for(int i=0; i<v; i++){
        int a, b;
        char c;
        scanf("%d%c%d",&a,&c,&b);
        if(c == '='){
            g1[a].push_back(b);
            g1[b].push_back(a);
        }
        else{
            edgs.emplace_back(a, b);
        }
    }
    for(int i=1; i<=m; i++){
        if(!comp[i]) dfs(i, ++piv);
    }
    for(auto &i : edgs){
        i.first = comp[i.first];
        i.second = comp[i.second];
    }
    sort(edgs.begin(), edgs.end());
    edgs.resize(unique(edgs.begin(), edgs.end()) - edgs.begin());
    for(auto &i : edgs){
        g2[i.first].push_back(i.second);
        g3[i.second].push_back(i.first);
        disj.uni(i.first, i.second);
    }
    for(int i=1; i<=piv; i++){
        cnd.push_back(pi(disj.find(i), i));
    }
    memset(dp1, -1, sizeof(dp1));
    memset(dp2, -1, sizeof(dp2));
    sort(cnd.begin(), cnd.end());
    for(int i=0; i<cnd.size();){
        int e = i;
        while(e < cnd.size() && cnd[i].first == cnd[e].first) e++;
        solve(i, e-1);
        i = e;
    }
    for(int i=1; i<=m; i++){
        if(ret[comp[i]] == -1){
            puts("?");
        }
        else{
            printf("K%d\n",ret[comp[i]]);
        }
    }
}

Compilation message

kovanice.cpp: In function 'int main()':
kovanice.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<cnd.size();){
                   ^
kovanice.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(e < cnd.size() && cnd[i].first == cnd[e].first) e++;
                 ^
kovanice.cpp:92:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&m,&v);
                               ^
kovanice.cpp:97:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%c%d",&a,&c,&b);
                                 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 30296 KB Output is correct
2 Correct 9 ms 30292 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 41988 KB Output is correct
2 Correct 199 ms 41952 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 33328 KB Output is correct
2 Correct 53 ms 33328 KB Output is correct
3 Correct 43 ms 33324 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 486 ms 54268 KB Output is correct
2 Correct 426 ms 54188 KB Output is correct
3 Correct 413 ms 54156 KB Output is correct
4 Correct 493 ms 66744 KB Output is correct
5 Correct 503 ms 66824 KB Output is correct