Submission #16647552

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <utility>
#include <chrono>
using namespace std;
constexpr int V_MAX = 500;
constexpr int Vemb_MAX = 3600;
static int emb[Vemb_MAX] = {}, inv[V_MAX] = {};
vector<pair<int, int>> G[V_MAX];
vector<int> Gemb[Vemb_MAX];
static int weight[V_MAX][V_MAX] = {};
static bool isEemb[Vemb_MAX][Vemb_MAX] = {};
chrono::system_clock::time_point start;
constexpr int timeLimit = 9900;
int V, E, Vemb, Eemb;
int CalcScore()
{
    int score = 0;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <utility>
#include <chrono>
using namespace std;

constexpr int V_MAX = 500;
constexpr int Vemb_MAX = 3600;

static int emb[Vemb_MAX] = {}, inv[V_MAX] = {};
vector<pair<int, int>> G[V_MAX];
vector<int> Gemb[Vemb_MAX];
static int weight[V_MAX][V_MAX] = {};
static bool isEemb[Vemb_MAX][Vemb_MAX] = {};
chrono::system_clock::time_point start;
constexpr int timeLimit = 9900;

int V, E, Vemb, Eemb;
int CalcScore()
{
    int score = 0;
    for (int now = 500; now < Vemb; now++)
    {
        if (emb[now] == -1)
            continue;
        for (int next : Gemb[now])
            if (emb[next] != -1)
                score += weight[emb[now]][emb[next]];
    }
    return score / 2;
}

inline int RandXor()
{
    static unsigned int x = 123456789, y = 987235098, z = 957398509, w = 879423879;
    unsigned int t;
    t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return abs((int)w);
}
int main()
{
    start = chrono::system_clock::now();
    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
        weight[u][v] = weight[v][u] = w;
    }
    cin >> Vemb >> Eemb;
    for (int i = 0; i < Eemb; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        Gemb[a].emplace_back(b);
        Gemb[b].emplace_back(a);
        isEemb[a][b] = isEemb[b][a] = true;
    }

    for (int i = 0; i < Vemb_MAX; i++)
        emb[i] = -1;
    for (int i = 0; i < V; i++)
        emb[i] = i;
    for (int i = 0; i < V_MAX; i++)
        inv[i] = -1;
    for (int i = 0; i < V; i++)
        inv[i] = i;

    int nowTime = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count();
    int nowScore = CalcScore();
    while (nowTime < timeLimit)
    {
        //適当に入れ替える
        int a = RandXor() % V, b = RandXor() % V;
        swap(emb[inv[a]], emb[inv[b]]);

        int nextScore = CalcScore();
        if (nextScore < nowScore) //まだ山登り
        {
            swap(emb[inv[a]], emb[inv[b]]);
            continue;
        }
        else
        {
            swap(inv[a], inv[b]);
            nowScore = nextScore;
        }

        nowTime = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count();
    }

    for (int i = 0; i < V; i++)
        cout << i + 1 << " " << inv[i] + 1 << endl;

    return 0;
}

Submission Info

Judge Result